二进制优化多重背包

我们设多重背包一共有 \(V\) 的容量，一共有 \(n\) 个物品，第 \(i\) 个物品价值为 \(v_i\)，代价为 \(w_i\)，数量为 \(c_i\)。

考虑暴力，将每个类型的物品都拆分成 \(c_i\) 个相同的物品，然后跑01背包，时间复杂度 \(O(V\sum{c_i})\)。

考虑二进制优化，将 \(w_i\) 个物品拆分成

\[ w_i=\sum_{k=0}^{2^{k+1}-1\leq w_i}{2^k} + r_i \]

可以证明，用这 \(\log(n)\) 项可以表示出取 \(0\leq x\leq w_i\) 中任意数量的该中物品，再用 01 背包解决，时间复杂度 \(O(V\sum{\log(w_i)})\) 。

个人认为该种方法比单调队列优化容易理解且代码较少。