关于 多重背包

问题描述：

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

问题特点：

第 i 件物品最多有 S_i 件，可以选择不超过 S_i 件的 i 物品放入背包中。

朴素版方程：

可以利用完全背包的想法，很容易得到：

for(int i = 1; i <= n; i ++)
        for(int j = 0; j <= m; j ++)
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i] * k] + w[i] * k);

但时间复杂度过高（ O(N*S*V) ），那么我们能不能像思考完全背包优化版那样来优化一下多重背包？

如何优化？

从状态转移方程入手，将其拆开：

可以发现，我们只能求出 max( dp[i,j-v] ) ，并不能求出橙色方框里的 max ，因此也就不能求出 max( dp[i,j] ) ，那么就不能直接利用完全背包的思想来解决。

这里呢就要用到一种比较神奇的优化方式了：二进制优化方式。

假设第 i 个物品有 s=1023 个，那我们难道真的要一个一个枚举出来吗？傻子才这么做，正常人都这么想：

把若干个第 i 个物品打包一起考虑，假设分成10组，第一组1个，第二组2个，第三组4个，第四组8个，……第十组512个，每组最多只能选一次，然后看一下是否能从这十组中拼凑出从0~1023 中任何一个数呢？那当然是。因此，我们可以将每组看作成一个小的“01背包问题”，也就是用10个新的物品来表示原来的第 i 个物品，然后我们枚举新的物品选或者不选就可以拼凑出第 i 个物品的所有方案了。（从枚举1024次缩小成枚举十次，log(n)的做法。）

但是！比如 s=200，可以分成1、2、4、8、16、32、64，注意，不能分出第七组128，因为 i 最多只有200个，而从1加到128有255个。从1加到64是127，200-127=73，所以第七组被分成73个。

总结：如果我们有 S 个物品，那么我们可以拆分成 logS 组，也就相当于 logS（logS向上取整）个新物品，新物品只能用一次，对新物品做一次01背包问题。

这样一来，由原先的复杂度 O(N*S*V) 优化成现在的时间复杂度 O(N*V*logS) 了。

最后也就是多了这些：

 1 int cnt = 0;//记录共有几组新物品
 2     for(int i = 1; i <= n; i ++)
 3     {
 4         int a, b, s;//价值、体积、个数
 5         cin >> a >> b >> s;
 6         int k = 1;
 7         while(k <= s)
 8         {
 9             cnt ++;
10             v[cnt] = a * k;
11             w[cnt] = b * k;
12             s -= k;
13             k *= 2;
14         }
15         if(k > 0)
16         {
17             cnt ++;
18             v[cnt] = a * s;
19             w[cnt] = b * s;
20         }
21     }
22 
23     n = cnt;

模板题：5. 多重背包问题 II - AcWing题库