题意：N(0 <=N <= 10)种钱，每种 ni(0 <= ni <= 1000) 张，每张 Di(1 <= Di <= 1000) 元，问合成不超过 cash(0 <= cash <= 100000) 的最大值是多少。
题目链接：http://poj.org/problem?id=1276
——>>多重背包。。
卡了一下内存。。所以，用滚动数组。。
#include <cstdio>const int MAXN = 200;
const int MAXC = 100000;int cash;
int N;
int ret;
int D[MAXN];
int cnt;
int dp[MAXC + 10];void GetNew(int n, int d)
{int num = 1;while (n >= num){D[++cnt] = d * num;n -= num;num <<= 1;}if (n){D[++cnt] = d * n;}
}void Read()
{int n, d;cnt = 0;scanf("%d", &N);for (int i = 1; i <= N; ++i){scanf("%d%d", &n, &d);GetNew(n, d);}
}void Solve()
{dp[0] = 1;for (int i = 1; i <= cash; ++i){dp[i] = 0;}for (int i = 1; i <= cnt; ++i){for (int j = cash; j >= 0; --j){dp[j] = dp[j];if (j - D[i] >= 0){dp[j] += dp[j - D[i]];}}}for (int i = cash; i >= 0; --i){if (dp[i]){ret = i;break;}}
}void Output()
{printf("%d\n", ret);
}int main()
{while (scanf("%d", &cash) == 1){Read();Solve();Output();}return 0;
}