多重背包的二进制思想优化

这是一道典型的多重背包题，下面链接

HDU 2191 http://acm.hdu.edu.cn/showproblem.php?pid=2191

介绍一下多重背包的二进制优化：

01 背包，有n 种不同的物品，每个物品有两个数值，价值。求最大价值。
多重背包，就是再给出每件物品给出确定的件数，也是求可得到的最大价值
最简单的就是在下一重循环枚举件数，取最大值。
二进制优化：把它的件数C 用分解成若干个件数，这里面数字可以组合成任意小于等于C的件数，而且不会重复，这样分解和二进制很相似，
每个数都可以分解成2的多少次幂的和，把他们相加即可。
15 = 1111 可分解成 0001 0010 0100 1000 四个数字
如果13 = 1101 则分解为 0001 0010 0100 0110 前三个数字可以组合成
7以内任意一个数，加上 0110 = 6 可以组合成任意一个大于6 小于13
的数，虽然有重复但总是能把 13 以内所有的数都考虑到了，基于这种
思想去把多件物品转换为，多种一件物品，就可用01 背包求解了。

code

 1 #include<cstdio> 
 2 #include<algorithm>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 
 7 int v[110],w[110],c[110];//v[]价值，w[]重量，c[]件数;
 8 int val[1010],wei[1010],dp[1010];
 9 
10 int main()
11 {
12     int t,n,m,cnt;
13     scanf("%d",&t);
14     while (t--)
15     {
16         cnt = 0;
17         memset(dp,0,sizeof(dp));
18         scanf("%d%d",&m,&n);
19         for (int i=1; i<=n; ++i)
20         {
21             scanf("%d%d%d",&v[i],&w[i],&c[i]);
22             for (int j=1; j<=c[i]; j<<=1)
23             {
24                 wei[++cnt] = j*w[i];
25                 val[cnt] = j*v[i];
26                 c[i] -= j;
27             }
28             if (c[i]>0)  
29             {
30                 wei[++cnt] = c[i]*w[i];
31                 val[cnt] = c[i]*v[i];
32             }
33         }
34         for (int i=1; i<=cnt; ++i)
35             for (int j=m; j>=val[i]; --j)
36                 dp[j] = max(dp[j-val[i]]+wei[i],dp[j]);
37         printf("%d
",dp[m]);
38     }
39     return 0;
40 }