多重背包

本篇对应源码见仓库 solutions/xcpc/algorithm/dp/knapsack-bounded/。

本题解只介绍使用二进制拆分方法($O\bigl(\sum_i\log c_i\cdot W\bigr)$)解决多重背包问题。朴素二维 $dp$ ($\displaystyle O\Bigl(\sum_i c_i\cdot W\Bigr)$) 和单调队列优化($O(\sum_i W)$)请自行寻找教程学习。

我的总结

• 解决多重背包的核心方法：转换为01背包。
• 二进制拆分核心就是通过二进制形式将每件物品划分为多组，然后对每组进行01背包。
• 重点需要理解的是，通过将一类物品进行二进制划分后可以组成任意数量的该类物品，这就是可行性。

下面重点围绕二进制拆分（Binary Splitting）这一多重背包的经典优化方法展开讲解。

一、为什么要用二进制拆分

• 问题所在：多重背包中第 $i$ 种物品有上限 $c_i$ 个，若直接按“$k=0\ldots c_i$”枚举，最坏需 $O(c_i)$ 步，对每件物品做一次 0–1 转移，总复杂度 $O\bigl(\sum_i c_i \times W\bigr)$，当 $c_i$ 很大或 $W$ 较大时常常超时。

• 核心思路：把 “$c_i$ 个相同物品” 拆成若干组，每组数量走二进制：$1,2,4,\dots$，再把余下的零散部分拆掉，拆分后组数仅 $O(\log c_i)$。这样整体拆分出的“0–1 物品”数是 $\sum_i O(\log c_i)$，再按 0–1 背包做一维滚动数组，令时间复杂度降为

  $O\Bigl(\sum_i \log c_i \times W\Bigr).$

二、二进制拆分步骤

设某种物品重量 $a$, 价值 $b$, 可选数量 $c$，划分后的总组数为 $cnt$:

1. 设当前剩余数为 $c$，拆分基数 $k = 1$。

2. 当 $k <= c$ 时：

   • 取本次拆分数 $k$。

   • 形成一个“0–1 物品”：w[++cnt] = k * a, v[cnt] = k * b。

   • 更新 $k \gets k \times 2$。

3. 重复直到 $k > c$。

4. 最后退出循环如果 $c$ 还有剩余，则再形成一个“0–1 物品”：w[++cnt] = c * a, v[cnt] = c * b。

举例：若 $c=13$，则拆分过程为

k=1: c-=1    → 1×a, 1×b
k=2: c-=2    → 2×a, 2×b
k=4: c-=4    → 4×a, 4×b
k=8: c=6(剩余) → 6×a, 6×b

共拆成 4 件“0–1 物品”，而不是 13 件。

三、实现要点

1. 提前拆分所有物品，得到一个新列表 splits，每项都是标准的 0–1 物品 (w',v')。

2. 一维滚动数组

   for(int i = 1; i <= cnt; i++) {
   	for(int j = W; j >= w[i]; j--) {
   				dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
   		}
   }

3. 空间与时间

   • 空间：$O(W)$

   • 时间：$O\bigl(\sum_i \log c_i \times W\bigr)$