YBTJ1269 【例9.13】庆功会

1、多重背包问题

有一个容量为V的背包和N种物品，第i种物品的体积是c[i]，价值是w[i]。每种物品最多可选a[i]个，求将哪些物品装入背包使得价值总和最大。

2、状态转移方程

与完全背包很像，区别就在于每个物品有上限a[i]，因此状态方程为：

dp[i][j] = max(dp[i-1][j-k*c[i]] + k*w[i]),  0<=k<=min(j/c[i], a[i])

3、朴素算法

三重循环：

for(int i=1; i<=n; i++) //物品
for(int j=v; j>=0; j--) //容量
  for(int k=0; k<=min(j/c[i], a[i]); k++) //个数
    f[j] = max(f[j], f[j-k*c[i]] + k*w[i]);

4、二进制拆分

把第i件物品拆分成多个物品，体积为c[i]*2^k，价值为w[i]*2^k，其中k满足c[i]*2^k<=v，这样，多重背包问题就转化成了01背包问题，即每个物品只能选或者不选。

for(int i=1; i<=n; i++) {//把i物品的a[i]个拆成若干个虚拟物品
  int s = a[i];
  for(int j=1; j<=s; j*=2) {
    c2[++last] = j*c[i];
    w2[last] = j*w[i];
    s -= j;
  }
  if(s) {//还有剩余
    c2[++last] = s * c[i];
    w2[last] = s * w[i];
  }
}

这样拆分的依据：对于第i件物品，不管选择几件，都可以用若干个2^k的和。例如：

0 = 都不选
1 = 2^0
2 = 2^1
3 = 2^1 + 2^0

于是，接下来就可以愉快的用01背包了。