Ⅲ · 多重背包 · O(V·log M)

多重背包：每种限选 M 件

多重背包处于 01 背包（第 1 讲）与完全背包（第 2 讲）之间：每种物品有件数上限 $M_i$ ，可被选取 0 至 $M_i$ 次。形式上，N 种物品各有费用 $C_i$ 、价值 $W_i$ 、上限 $M_i$ ，在容量 V 下求所选物品总价值最大。对每种逐一枚举选取件数 k ∈ {0..Mᵢ} 的朴素 DP，复杂度 $O(NV\cdot \bar{M})$ ，在 M̄ 大时难以承受。本讲核心是二进制拆分：把「 $M_i$ 件可选」等价转化为约 $\log M_i$ 件 01 物品，从而降至 $O(NV\cdot \log \bar{M})$ 。

1 · 问题描述

N 种物品，第 i 种费用为 $C_i$ 、价值为 $W_i$ 、件数上限为 $M_i$ 。给定容量上限 V，要求在所选物品费用之和不超过 V 的前提下，最大化价值之和。状态与 01 背包 / 完全背包同构：记 $F[i][v]$ 为「在物品 1..i 中选取（第 j 种至多 Mⱼ 件）、总费用不超过 v 时的最大价值」。差异仅在「对每种物品有多少种选取数量」——01 背包两种、完全背包 $\lfloor V/C_i\rfloor +1$ 种、多重背包 $M_i+1$ 种。朴素转移方程多一层对 k 的枚举：

F[i][v] = max(0 ≤ k ≤ Mᵢ) ( F[i−1][v − k·Cᵢ] + k·Wᵢ )

初值约定：本讲采用第 1 讲 §6 建立的不必装满默认(F[0..V] = 0)，对所有背包问题通用。恰好装满变体同样适用——转移不变，仅初值改为 F[0]=0、 $F[1..V]=-\infty$ ；当某容量在 $M_i$ 约束下确实不可达时，最终 $F[V]$ 将保留 $-\infty$ 。若进一步退化到不关心价值、只问「能否凑出 V」的可行性形态，聚合算子由 max 改为 OR，见第 9 讲（变种与统一）「最少件数 / 可行性（有解判定）」一节；本讲 §3 的 NOTES「可行性问题的 O(NV) 算法」另给出一种把件数余量编码进状态值、达到 $O(NV)$ 的可行性专用解法。

对照	01 背包	多重背包（本讲）	完全背包
枚举量	2 种	Mᵢ + 1 种	⌊V/Cᵢ⌋+1 种
约束	每件至多 1 次	每种至多 Mᵢ 件	每种无限次
取件数 k	k ∈ {0, 1}	k ∈ {0, …, Mᵢ}	k ∈ {0, …, ⌊V/Cᵢ⌋}

1.1 · 为什么多重背包「有限制」反而比完全背包「无限制」更难？

上方对比显示完全背包的枚举量（ $\lfloor V/C_i\rfloor +1$ 种）通常超过多重背包（ $M_i+1$ 种）——按「枚举量主导复杂度」的直觉，完全背包的渐进复杂度应当最高，但第 2 讲已证它只需 $O(NV)$ 。这与多重背包「 $O(NV\cdot \bar{M})$ 难以承受」看似矛盾。

矛盾的根源在于本层递推这一特权：完全背包的一维实现 $F[v] = \max (F[v], F[v-C_i] + W_i)$ 中， $F[v-C_i]$ 已是本层值，蕴含「物品 i 已被选若干次」的最优，故「再多选一件」只需一次比较——整层对 k 的枚举被摊销进 v 的递增循环。同样的本层递推用在多重背包上则失效： $F[v-C_i]$ 可能已用满 $M_i$ 件，「再加一件」将违反约束。Mᵢ 限制的存在恰恰破坏了本层递推——只能显式枚举 k 来记账件数， $O(NV\cdot \bar{M})$ 由此而来。

因此 01 背包(M=1)与完全背包( $M=\infty$ )是两端最易处理的形态，中间的「有限多件」反而最棘手。

多重背包的难点在于：既不能借完全背包的本层递推（件数不受控）、也不能朴素枚举 k 而不付出 $O(\bar{M})$ 代价。二进制拆分正是绕开这一两难的标准做法——把多重背包转化为一种本来就能高效求解的 01 背包形态。其精妙处不在「加速朴素枚举」，而在把件数约束 $M_i$ 编码进约 $\log M_i$ 件每包仅可一选(once-or-none)的包——01 背包的逆序循环天然保证「每包至多一次」，件数约束被分解结构隐式吸收。

NOTES · 记号约定 ·「前 i 件」的读法 ·「朴素」一词的跨讲歧义

本讲及后续各讲沿用以下惯例：状态 $F[i][v]$ 中的 i 是候选集合的上界，即允许从物品 {1, …, i} 中选取（多重背包下第 j 种至多 Mⱼ 件）,v 是总费用上限。i 从 0 增至 N 对应「逐步把每种物品纳入候选范围」——这是正向 DP 的视角。

读者偶有把「前 i 件」误读为「剩余未判定的 i 件」的情况，后者对应逆向 DP（以 $G[j][v]$ 表示「从第 j 件到第 N 件中选取的最大价值」，边界 G[N+1][v]=0，答案为 $G[1][V]$ ）。两种写法算法上等价，本讲采用前一种。

术语 ·「朴素枚举」与「朴素 DP」

「朴素(naive)」意为「不做任何优化的直接做法」。本讲多处出现的「朴素 DP / 朴素枚举」均特指对每种物品逐一枚举选取件数 k ∈ {0..Mᵢ} 而不做任何件数压缩的实现——即把 §1 转移方程直接照搬循环。复杂度 $O(NV\cdot \bar{M})$ 来自三因子相乘：N 种物品 × V 个容量取值 × 每种 $M_i+1$ 个 k 选项。二进制拆分把第三个因子从 $M_i+1$ 压到 $\log _2(M_i+1)+1$ 件 once-or-none 包。

跨讲歧义说明：同一「朴素」二字在第 1 讲 §7 与第 2 讲 §4 中指朴素树递归（无记忆化的指数级实现），与本讲「对件数 k 直接枚举」的朴素 DP 语义不同。前者强调「递归未缓存子问题」，后者强调「循环未压缩枚举量」——二者都属「未做优化的直接做法」，但优化目标不同。

2 · 二进制拆分与覆盖性验证

承完全背包（第 2 讲）「前瞻 · 通向多重背包的二进制拆分」一节：把「每种 $M_i$ 件可选」重写为约 $\log M_i$ 件 once-or-none 包后，复杂度立即由 $O(NV\cdot \bar{M})$ 降至 $O(NV\cdot \log \bar{M})$ ，且由 01 约束的反推，基只能取二进制。该节已给出动机、论证与最小示例，本节补足最后一步——这组包的标准构造形态。

把 $M_i$ 拆为系数 ${1, 2, 4, \dots , 2^{t-1}, R}$ ，其中 $t = \lfloor \log _2(M_i+1)\rfloor$ 、 $R = M_i - (2^t - 1)$ 。每个系数 k 对应一件「打包后的物品」：费用 $k\cdot C_i$ 、价值 $k\cdot W_i$ ，在 01 背包中至多被选取一次。这样，任意 ${0 \le κ \le M_i}$ 件原物品的组合，均可由若干打包件的子集和精确表达。朴素方程的 $O(NV\cdot \bar{M})$ 由此降至 $O(NV\cdot \log \bar{M})$ 。

图 2-1 ·

M_i

的二进制拆分与覆盖区间。可拖动

M_i

观察系数集变化，单击任一

k

查看其子集表达。

NOTES · 二进制拆分手算 (M=13) · 覆盖性 · 边界 M 值 · 退化为完全背包

按算法 $k = 1, 2, 4, \dots$ 逐次拆出系数，直到 k 不小于剩余值，最后将剩余部分作为「尾巴」R 单独成一件：

初值: M = 13, k = 1, 系数集 = {}
第 1 步: k=1 < 13   → 系数 += 1, M = 12, k = 2
第 2 步: k=2 < 12   → 系数 += 2, M = 10, k = 4
第 3 步: k=4 < 10   → 系数 += 4, M =  6, k = 8
第 4 步: k=8 ≥ 6    → 退出循环
收尾:                系数 += M = 6
最终系数集 = {1, 2, 4, 6}, 和 = 13 ✓

覆盖性：前 t 个 2 的幂（此例 {1,2,4}）的子集和恰为 {0..7}，即覆盖 $[0, 2^t-1]$ 。再加入尾巴 R=6，可覆盖 [6,13]；两段在 {6,7} 处重叠，共同覆盖 [0,13]。一般情形下，前 t 个 2 的幂覆盖 $[0, 2^t-1]$ ，加尾巴后扩至 [0, M]，且任一选取均不超过 M。

覆盖手算 · 全部 k ∈ [0,13] 的子集表达

想取 k 件	选哪些包	验证
0	∅	0 ✓
1	{1}	1 ✓
2	{2}	2 ✓
3	{1,2}	1+2=3 ✓
4	{4}	4 ✓
5	{1,4}	1+4=5 ✓
6	{2,4}	2+4=6 ✓
7	{1,2,4}	1+2+4=7 ✓
8	{2,6}	2+6=8 ✓
9	{1,2,6}	1+2+6=9 ✓
10	{4,6}	4+6=10 ✓
11	{1,4,6}	1+4+6=11 ✓
12	{2,4,6}	2+4+6=12 ✓
13	{1,2,4,6}	1+2+4+6=13 ✓

14 个原始选项 → 4 件 once-or-none 打包件。每个「包」在 01 背包里费用为 $C\cdot 包大小$ 、价值为 $W\cdot 包大小$ ,01 背包逆序循环天然保证「每包至多一次」。

系统化构造规则：上表对每个 k 的取包并非任意，而是「前 t 项二进制 + 余数包」的标准规则。当 $k < 2^t$ （此例 ${2^t=8}$ ）时，用前 t 项 {1,2,4} 的二进制位表示，即 k 二进制中为 1 的位对应取那个包（如 k=6 → {2,4}，因 ${6=110_2}$ ）；当 $k \ge 2^t$ 时，先取余数包 R，再用前 t 项凑出 $k-R \in [0, 2^t-1]$ （如 k=10 → 先取 {6}，再凑 4 得 {4,6}）。两段在 $[R, 2^t-1]$ （此例 [6,7]）处重叠，故同一 k 可有多种合法表达。

非唯一性附注：对 k=6,7，除上表的 {2,4} 与 {1,2,4} 外，还存在合法表达 {6} 与 {1,6}——覆盖性只要求存在而非唯一。读者也可在上方演示拖动 $M_i$ 、单击不同 k 互动验证。

总件数公式

对一般 M，二进制拆分总件数为 $\lceil \log _2(M+1)\rceil$ :

M+1 不是 2 的幂时：件数 $= \lfloor \log _2(M+1)\rfloor + 1$ （前 t 项二进制 + 1 个余数包）
$M+1 = 2^t$ 恰为 2 的幂时：件数 = t（R=0，无余数包）

边界 M 值的拆分行为

M	系数集	件数	⌈log₂(M+1)⌉
1	{1}	1	1
2	{1, 1}	2	2
3	{1, 2}	2	2
4	{1, 2, 1}	3	3
7	{1, 2, 4}	3	3
8	{1, 2, 4, 1}	4	4
13	{1, 2, 4, 6}	4	4
15	{1, 2, 4, 8}	4	4
16	{1, 2, 4, 8, 1}	5	5

M=2 为何不拆为 {2} 一件？ 因 01 物品的语义是 once-or-none，一件 {2} 只能整体取 0 或 2 件，无法表达「取 1 件」。必须真有两件可独立选取的包，故拆为 {1,1}。同理 M=4 → {1,2,1} 中的两个 1 是为表达奇数件 {1,3} 所必需； $M=8=2^3$ 时由于 $R=8-7=1$ 出现第二个 1。重复元素不影响覆盖性，但每个打包件在 01 背包中被独立对待。

边界优化 · 退化为完全背包

若 $C_i\cdot M_i \ge V$ ，则即便完全不限制件数，选取数量也不可能达到 $M_i$ （容量先耗尽），件数上限实际不起作用。此时应直接以完全背包求解，避免二进制拆分的额外开销：

function MultiplePack(F, C, W, M) {
  if (C * M >= V) {       // 上限不可达 → 退化为完全背包
    CompletePack(F, C, W);
    return;
  }
  // 否则按二进制拆分展开为若干件 01 物品...
}

当 $M_i$ 极大（如 10⁹）、V 适中（如 10³）时，此优化尤为重要——可避免约 30 次 $O(V)$ 的内层调用，直接 $O(V)$ 求解。

为何条件用 ≥ 而非 >：严格 $C_i\cdot M_i > V$ 显然让上限失效。等号情形 $C_i\cdot M_i = V$ 看似仍有约束，实则等价：完全背包的天然件数上界为 $\lfloor V/C_i\rfloor$ ，在此条件下恰为 $M_i$ ——即便完全背包不显式限制件数，自然循环也最多选到 $M_i$ 件，与原约束一致。故用 ≥ 将等号情形并入退化分支，正确且更省一次拆分。

二进制拆分的元思想。「用 $O(\log M)$ 个元素表达 [0, M] 内所有整数」超出背包问题本身：倍增 / Sparse Table（每步跳 2ᵏ,log n 次覆盖任意查询）、快速幂（ $a^M$ 拆为 $a^1, a^2, a^4, \dots$ 的若干乘积）、二进制位表示（任一非负整数唯一表为 $Σ b_k\cdot 2^k$ ）皆同源。{1, 2, 4, …, 2ᵗ⁻¹, R} 是件数最少且构造最规范的标准形式；由信息论下界，任何其他构造的件数都不低于 $\lceil \log _2(M+1)\rceil$ 。二进制基并非唯一的覆盖性构造：任何「系数和为 M 且子集和能表达 [0, M] 内每个整数」的多重集同样满足覆盖性——例如 M=13 也可拆为 {2, 3, 4, 4} 或 {1, 3, 4, 5}，只是件数多于标准形式，{1, 2, 4, …, R} 的件数最少。信息论下界的来由：n 件 once-or-none 的 01 物品共有 ${2^n}$ 个子集，至多区分 ${2^n}$ 个状态，而所需区分的件数取值有 M+1 个（0 至 M），故 ${2^n \ge M+1}$ ，即件数 $n \ge \lceil \log _2(M+1)\rceil$ 。

3 · 复杂度对比 · 朴素枚举 vs 二进制拆分

下面将朴素方法的操作数 $N\cdot V\cdot (M_i+1)$ 与二进制拆分的 $N\cdot V\cdot \lceil \log _2(M_i+1)\rceil$ 并排展示。可调整 $M_i$ 与 V，观察两者在不同规模下的差距：当 $M_i$ 较小（数十量级）时差异不显著，而当 $M_i$ 达数百量级以上，对数增长相对线性增长形成数量级差距。

NOTES · 可行性问题的 O(NV) 算法 · 进一步压缩复杂度

若题目仅询问「容量 V 是否能被恰好填满」，不关心价值最大化，则可设计一种更优的状态：

$G[i][j]$ = 在物品 1..i 中选取（第 j′ 种至多 Mⱼ′ 件）恰好填满容量 j 后，第 i 种物品最多还能剩余的件数。 $G[i][j] = -1$ 表示该状态不可达；否则 ${0 \le G[i][j] \le M_i}$ 。

转移分以下情形给出，每个 (i, j) 只做 $O(1)$ 运算：

不取第 i 种:  若 G[i-1][j] ≥ 0, 则 G[i][j] = M_i;
续取第 i 种:  否则若 j ≥ C_i 且 G[i][j - C_i] ≥ 1,
              则 G[i][j] = G[i][j - C_i] - 1;
默认不可达:   G[i][j] = -1。
初值: G[0][0] = 0, G[0][j>0] = -1。
答案: G[N][V] ≥ 0 即可行。

该设计的精妙之处：把「已选取多少件」信息编码进状态值，而非以一维 k 显式枚举——「不取」情形的「Mᵢ」表示「刚开始考虑第 i 种、尚未选取任何一件」；「续取」情形表示「已选若干件、件数余量减 1」。两种正向情形覆盖全部可达转移，默认的「不可达」情形将其余状态标记为不可达。因此对 $k \in [0, M_i]$ 的逐一枚举被隐式吸入到 G 的递推中，复杂度由 $O(NV\cdot \log \bar{M})$ 进一步降至 $O(NV)$ 。

3.1 · 单步看 O(NV) 可行性表怎么填

下面把上述 $G[i][j]$ 表逐格填出来（行 = 物品上界 i，列 = 容量 j）。每格只做 $O(1)$ 判断，走不取情形（不取第 i 种，继承上一行的可达性、余量重置为 $M_i$ ）、续取情形（续取一件，从左侧 $j-C_i$ 处的余量减一），否则默认不可达 −1。绿格里的数字就是「第 i 种还剩几件可选」。

4 · 应用案例 · 限领券组合

把多重背包应用于电商场景：平台对每种满减券设置每用户限领上限 $M_i$ 张（如「满 50-12 每人限领 5 张」「满 500-150 仅可领 1 张」）。把券门槛视为费用 C、单张减免视为价值 W、限领数量视为件数上限 M，在固定购物车总额 V 下求最大总减免即标准多重背包。调整总额观察最优组合变化；某券达限领上限时以红色 MAXED 角标标识。

NOTES · 贪心方法的局限 · Mᵢ 配额陷阱 · 关键概念出处 · 通向第 4 讲

读者可能会问：既然第 1 讲 §2（01 背包）与第 2 讲 §5（最少硬币数）中贪心策略都会失败，多重背包是否也有贪心反例？答案是肯定的——且失败模式更尖锐，因为 $M_i$ 件数约束会让贪心提前耗尽「配额」，剩余容量无法吸纳本可承担的高价值物品。

取 V=5、两种物品 {(C,W,M)} = {(3,4,1), (2,3,2)}:

方法	选取方案	费用	价值
按性价比贪心	(2,3)×2 件（性价比 1.5 最高，取满 M）	4	6
DP	(3,4)×1 + (2,3)×1	5	7

贪心放弃 (3,4) 因其性价比 4/3 ≈ 1.33 略低于 (2,3) 的 1.5；但 (2,3) 在 M=2 件后耗尽「配额」，剩余 1 容量不足以装下 (3,4) 的费用 3。DP 看到的全局：放弃 (2,3) 的第二件配额，改选 (3,4)，总价值从 6 升到 7。

这与第 1 讲 §2 与第 2 讲 §5 共同构成「贪心在背包系列中通用失败」的三讲对偶，失败模式各不同：

01 背包（第 1 讲 §2）：贪心失败因「无法回头放弃高单价物品换取多件组合」
最少硬币数（第 2 讲 §5）：贪心失败因「贪取大面值后剩余金额需用过多小面值填补」
多重背包（本案例）：贪心失败因「Mᵢ 配额耗尽后，剩余容量无法吸纳其他物品」——多重背包特有，01 与完全背包都不会出现

共同教训：背包及其变形几乎总需要 DP 才能保证最优；贪心只在极特殊结构（如 matroid、正则币制等）下偶然成立。

关键概念出处

多重背包在英文文献中称 bounded knapsack problem（注意不要与 multiple-choice knapsack problem 混淆，后者指「每组中至多选一件」的分组场景，对应本系列第 6 讲）。二进制拆分思想最早见于 Lawler & Bell, 1966 关于「整数线性规划的隐式枚举」的早期工作。可行性问题的 O(NV) 算法亦可视为「用单调队列优化朴素枚举」的特例，见 Pisinger, A minimal algorithm for the bounded knapsack problem, INFORMS Journal on Computing, 2000。

延伸阅读 · 单调队列优化

多重背包的另一类优化路径是单调队列：对每种物品，将朴素方程中的 max 改写为对一个滑动窗口的最大值查询，可达到 $O(NV)$ 。该方法实现较复杂；在工程实践中，二进制拆分因实现简单、常数较小，仍是首选方法。

通向第 4 讲 · 混合背包

第 4 讲将把 01 背包、完全背包、多重背包三种物品混合出现于同一问题。届时主循环只需根据物品类型分发到不同的 Pack 过程(ZeroOnePack / CompletePack / MultiplePack)，无需引入新算法——这一分发模式正是基于前三讲对每种背包封装为独立过程的设计。

5 · 应用案例 · 批发市场 SKU 进货（起订 / 库存双约束）

本节是第 2 讲「同种平台券反复领取」的经营者对偶：小卖部老板拿一笔进货资金去批发市场，把进货资金视为容量 V、批发进价视为 C、单件毛利视为 W，求毛利之和最大。若每种 SKU 可任意件进货，即标准完全背包（第 2 讲）；引入两类现实约束后，升级为多重背包:

起订量 $\underline{k}_i$ ：若进货第 i 种 SKU，一次至少 $\underline{k}_i$ 件（批发商最小成箱量 / 最小订单门槛）。
库存上限 $\bar{k}_i$ ：第 i 种 SKU 当日批发市场存量——多重背包件数上限 $M_i$ 的现实由来。

约束写作 $k_i \in [\underline{k}_i, \bar{k}_i]$ 。可归约为标准多重背包：先扣除「强制基础采购」 $Σ \underline{k}_iC_i$ 与对应毛利，在剩余资金 V' = V − Σ k̲ᵢCᵢ 上对「追加件数」k'ᵢ ∈ [0, k̄ᵢ − k̲ᵢ] 做标准多重背包。若 $Σ \underline{k}_iC_i > V$ 则问题不可行——资金不足以覆盖起订总额。下方所有字段均可点击编辑，末尾占位卡可新增、卡片右上 × 可删除。

小结。多重背包卡在 01 与完全之间：件数上限 $M_i$ 破坏了完全背包的本层递推，逼出朴素的 $O(NV\cdot \bar{M})$ 。二进制拆分把每种的 $M_i+1$ 个件数选项压成约 $\log M_i$ 件 once-or-none 包，退化成 01 背包做，得到 $O(NV\cdot \log \bar{M})$ ；特例还能用单调队列 / 状态语义重设计降到 $O(NV)$ 。第 4 讲（混合背包）把三类物品置于同一问题中，按 type 分发到各自的 Pack 过程。