多重背包¶

问题描述¶

有 $n$ 种物品（每种物品有 $N_{i}$ 个 ）和一个容量为 $W$ 的背包，每个物品有重量 $w_{i}$ 和价值 $v_{i}$ 两种属性，要求：选若干物品放入背包，使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量

与完全背包问题类似，考虑对每件物品，枚举其选择件数，得到 状态转移方程：

f[i][j]=max(f[i-1][j-k*w[i]])+k*v[i] ，其中 0<=k<=N[i]

另一种思路是将其转化为 0-1 背包问题：

只要把 “种” 换成 “个” 就好了，也就是把 每种物品有 $N_{i}$ 个 拆成 $N_{i}$ 个相同的物品 ，再用 0-1 背包的方法就可以求解了

可以发现，两种思路的时间复杂度都是 $O (W \times \sum_{i = 1}^{n} N_{i})$

可以看到，上面两种思路实际上都是在考虑第 i 种物品时，将 f[i] 拆成 $N_{i}$ 个子状态，每个子状态对应一件 i 物品，再对每个子状态应用决策（取-不取）

如果选两件 i 物品要怎样做呢？很明显，在拆出来的 $N_{i}$ 个子状态任选两个应用决策 “取”，其他的都应用决策 “不取” 即可。可以发现，任选两个 将导致大量重复操作

怎么优化呢？

我们可以在拆分时不把 f[i] 完全拆散，而是采用倍增的思想，将其拆成大小为 1,2,4,8,... 的小块

我们知道，任意正整数都能表示为 2 的不同幂次之和 ，所以这样拆分后，不管选几个都可以通过选 “小块” 实现了

如果 N[i] 不是 2 的连续幂次之和 怎么办呢？把多出来的作为一个块就好了，块大小为

N - 2^{⌊ \log_{2} (N + 1) ⌋ - 1}

比如： $18 = (1 + 2 + 4 + 8) + 3$