多重背包模板

状态转移方程：
dp[i][v]=max{dp[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

 1 void ZeroOnePack(int cost,int weight)
 2 {
 3     int j;
 4     for(j=V;j>=cost;j--)
 5         dp[j]=max(dp[j],dp[j-cost]+weight);
 6 }
 7 void CompletePack(int cost,int weight)
 8 {
 9     int j;
10     for(j=cost;j<=V;j++)
11         dp[j]=max(dp[j],dp[j-cost]+weight);
12 }
13 void MultiplePack(int cost,int weight,int cnt)
14 {
15     int k=1;
16     if(cost*cnt>=V){  //总价值大于V时，等价于完全背包
17         CompletePack(cost,weight);
18         return;
19     }
20     while(k<cnt){  //否则，按二进制思想分解该物品
21         ZeroOnePack(cost*k,weight*k);
22         cnt-=k;
23         k*=2;
24     }
25     ZeroOnePack(cost*cnt,weight*cnt);
26 }

View Code

多重背包 模板

多重背包模板