分析和思路:
建立一个hash的表达式,如果那个重量能够称出来,就给它赋值1.然后把所有的砝码的重量进行累加,出现新的重量就赋值1,重复的也赋值1,在遍历整个v[i]=1的个数,就是能够称出的重量总数。
需要考虑一个问题,如何将已有的砝码总量都进行累加?如果有多少组,就需要列几个循环吗?10个组10个循环?显然不可行。先求一个最大的重量,然后再在最大的重量上逆序,为什么要逆序?逆序的原因就是新一轮循环开始的起点会越来越大,从而保证
前面所有的值没有被覆盖,而且后面的值也不会被覆盖。只会不断的更新,然后保证最终的结果是正确的。
1 #include <iostream> 2 3 using namespace std; 4 5 int main() 6 { 7 int n;//砝码数 1~10 8 while(cin >> n) 9 { 10 int w[10] = {0};//重量 1~2000 11 int num[10] = {0};//数量 1~6 12 //每个砝码重量 13 for(int i = 0; i < n; i ++) 14 cin >> w[i]; 15 //相应的数量 16 for(int i = 0; i < n; i ++) 17 cin >> num[i]; 18 19 int v[120000] = {0};// 10 * 2000 *6 = 120000 20 int maxw = 0; 21 for(int i = 0; i < n; i ++) 22 maxw += w[i] * num[i]; 23 24 v[0] = 1; 25 //类似背包问题 26 for(int i = 0; i < n; i ++) 27 for(int j = maxw; j >= 0; j--) 28 for(int k = 1; k <= num[i]; k ++) 29 { 30 if(v[j] == 1) 31 v[j + k * w[i]] = 1; 32 } 33 34 int res = 1; 35 for(int i = 1; i <= maxw; i ++) 36 if(v[i] == 1) 37 res ++; 38 39 cout << res << endl; 40 41 } 42 43 return 0; 44 }