算法之动态规划01背包类似问题-称砝码

算法之动态规划01背包类似问题-称砝码

 

分析和思路:

建立一个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 }

 

上一篇:快速搭建Python开发环境


下一篇:【PG数据库】PG数据库的安装及连接方法