多重背包

问题概述：

有N种物品和一个容量为V的背包，每种物品的价值为p[i],且每种物品至多有N[i]件可用，问怎样放可以使背包内价值最大。

解决：

多重背包问题可以转化成0-1背包问题来求解，就是多了个分解，把每种物品的件数N[i]用二进制分解成若干件数，

例如：7 的二进制是111 ，它可以分解成 001,010，100 三个数，也就是1,2,4；

这里面数字可以组合成任意小于等于N[i]的件数，而且不会重复。

为了更好的理解它，也可以把它想象成把 N[i] 件零散的物品打包成若干件稍大份的物品，这样就可以直接用0-1背包来求解啦。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #define ll long long 
 5 #define MAX 50005 
 6 using namespace std;  //  多重背包 
 7 ll f[MAX];
 8 ll w[MAX],p[MAX]; 
 9 int main()
10 {
11     int n,v; 
12     while(scanf("%d%d",&n,&v)!=EOF) //输入 ： 有 n 件物品，背包容量为 v 
13     {
14         int cnt=0,wt,pr,ct;
15         memset(w,0,sizeof(w));
16         memset(p,0,sizeof(p));
17         memset(f,0,sizeof(f));
18         for(int i=0;i<n;i++)  
19         {
20             scanf("%d%d%d",&wt,&pr,&ct);  // 输入每件物品的  重量、价值、数量 
21             for(int j=1;j<=ct;j<<=1)  // 开始按照二进制分解每件物品 
22             {
23                 w[cnt] = j*wt;  // 分别存进 重量数组 和价值数组 里 
24                 p[cnt++] = j*pr;
25                 ct-=j;  //  原来的数量减去分出的数量 
26             }
27             if(ct>0)  // 剩余没分完的 
28             {
29                 w[cnt] = ct*wt;
30                 p[cnt++] = ct*pr;
31             }
32         }
33         for(int i=0;i<cnt;i++)  // 分完后就可以用 0-1背包 来求解啦 
34         {
35             for(int j=v;j>=w[i];j--)
36             f[j] = max(f[j],f[j-w[i]] + p[i]);
37         }
38         printf("%lld
",f[v]);
39     }
40     return 0;
41 }

如果有什么不对的地方，还请各位大神批评指正^-^