大意：
有n种物品
告诉你每种物品的价值和数量
问你能拼凑出1--m之内的多少个数
分析：
多重背包
代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 100005; 7 int dp[maxn]; 8 int num[maxn], va[maxn]; 9 int vo[maxn]; 10 int n, m; 11 int tot; 12 13 int solve() { 14 int cnt = 0; 15 memset(dp, 0, sizeof(dp)); 16 for(int i = 1; i < tot; i++) { 17 for(int j = m; j >= vo[i]; j--) { 18 dp[j] = max(dp[j], dp[j - vo[i]] + vo[i]); 19 } 20 } 21 for(int i = 1; i <= m; i++) { 22 if(dp[i] == i) cnt++; 23 } 24 return cnt; 25 } 26 27 int main() { 28 while(scanf("%d %d",&n, &m) && ( n + m ) ) { 29 for(int i = 1; i <= n; i++) { 30 scanf("%d",&va[i]); 31 } 32 for(int i = 1; i <= n; i++) { 33 scanf("%d",&num[i]); 34 } 35 tot = 1; 36 for(int i = 1; i <= n; i++) { 37 for(int k = 1; k <= num[i]; k *= 2) { 38 vo[tot++] = k * va[i]; 39 num[i] -= k; 40 } 41 if(num[i]) vo[tot++] = num[i] * va[i]; 42 } 43 printf("%d ",solve()); 44 } 45 return 0; 46 }