Ⅱ · 完全背包 · F[v] · v 顺序

完全背包：每种可无限次选

完全背包是 01 背包（第 1 讲）的推广：把「每件物品至多被选取一次」放宽为「每种物品可被选取无限多次」。形式上仍是 N 种物品、费用 $C_i$ 价值 $W_i$ 、容量 V，求最大总价值。值得注意的是：完全背包与 01 背包的 state、transition 几乎相同，而一维实现的差异仅在一个循环方向。本讲从这一关键差异出发，介绍朴素方法、空间压缩、典型变形（凑零钱方案数与最少件数），并讨论实际应用。

1 · 问题描述

给定 N 种物品，第 i 种费用为 $C_i$ 、价值为 $W_i$ ，可被选取的次数不受限制；容量上限为 V。求在所选费用之和不超过 V 的前提下最大化价值之和。

引入一维 state $F[v]$ =「容量为 v 时所能取得的最大价值」。对每种物品考察「再选取一件该种物品」时，所需的子问题恰是本层的 $F[v-C_i]$ （允许该种物品已被选取过），而非上一层。在一维数组中「本层」意味着读 $F[v-C_i]$ 时该位置已被本轮更新——由于 $v-C_i < v$ ，只有 v 从小到大遍历时才成立。于是完全背包的 v 更新方向由 01 背包的「递减」反转为「递增」：循环顺序不是约定，而是让一维数组在读时拿到正确层值的唯一时序。

01 背包 · v 递减(V → Cᵢ): $F[i][v] = \max (F[i-1][v], F[i-1][v-C_i]+W_i)$ ——选的那支读上一层 $F[i-1]$ ，所以同一件物品最多算进去一次。

完全背包 · v 递增(Cᵢ → V): $F[i][v] = \max (F[i-1][v], F[i][v-C_i]+W_i)$ ——选的那支读本层 $F[i]$ （已含本件），于是能反复叠加同一件。

初值约定：本讲采用第 1 讲 §6 建立的不必装满默认（F[0..V] = 0，任意容量均可由「什么都不选」得到价值 0）。恰好装满变体（F[0]=0，其余 $-\infty$ ）在本讲 §5 · 最少硬币数中以 min 聚合形态出现。

NOTES · 记号约定「前 i 件」的读法

state $F[i][v]$ 中的 i 是候选集合的上界，即允许从物品 {1, 2, …, i} 中选取（完全背包下每种可任意件）,v 是总费用上限。i 由 0 涨到 N 对应「逐步把每种物品纳入候选范围」——这是正向 DP 的视角。

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

2 · 循环方向与算法差异

下面把 01 背包与完全背包的一维实现并列运行于同一组数据。两段代码的唯一区别在内层循环 v 的方向：01 递减、完全递增。蓝色标示当前被读取的 $F[v-C_i]$ ,金色标示当前被写入的 $F[v]$ ，可观察两种实现在同一时刻所读取的来源差异。

同一组数据下两种算法的对比。取 V=6、两种物品 (C,W) = (2,3),(3,4)。01 背包最优值 7：各选一件，总费用 2+3=5、价值 3+4=7。完全背包最优值 9：选 3 件物品 1，总费用 2×3=6、价值 3×3=9。两者差 2 完全来源于循环方向——同一份 state、同一组数据，仅 v 的更新方向反转，即得到两种语义截然不同的结果。

3 · 同种物品复用的机制

以单种物品 (C,W) = (2,3)、V=6 为例。v 递增遍历时， $F[v-2]$ 在被读取前已于本轮被写入新值，其中已包含「选取该种物品一次」的贡献。因此当 $F[v]$ 再次基于 $F[v-2]$ 更新时，等价于「在已有选取的基础上再选一件」——这正是允许同种物品被无限选取的机制。点击下方步骤胶带可定位至任意单元。

每个单元下方的方块数表示：在该 $F[v]$ 状态背后，该种物品（默认 C=2）已被选取的件数。v=4 时累计 2 件，v=6 时累计 3 件——完全背包正是在一维数组中以这种「隐式复用」实现同种物品被多次选取的语义。

4 · 凑零钱（一）· 方案数：组合 vs 排列

本节切换问法：前三节求「最大价值」，现在改问「用给定面值凑出目标金额有多少种方案」。每种面值可无限次使用，本质上仍是完全背包。DP 框架几乎原样保留，唯一改动是把聚合操作由 max 换成求和——「凑成 v 的方案数」=「凑成 v−C 的方案数，再加一枚 C」在所有面值上的累加，即 $F[v] += F[v-C]$ 。

但聚合改为加法后，两层循环的嵌套顺序突然变得关键：

外层枚举硬币、内层枚举金额：每种面值只被处理一次，每个凑法作为「多重集合」被数 → 组合数（不区分顺序）。
外层枚举金额、内层枚举硬币：每个金额都把所有面值轮一遍，凑法被展开成「按出现顺序的序列」→ 排列数（区分顺序）。

以 V=3、面值 {1,2} 为例：外硬币内金额得 F[3]=2({1,1,1},{1,2})；外金额内硬币得 F[3]=3(1+1+1, 1+2, 2+1)。同一组数据、同一递推骨架，仅嵌套顺序之差就把两类计数问题分了开。

5 · SICP 案例 · 三种实现的代价对比

SICP §1.2.2 以「用美式硬币凑零钱」作为 tree recursion 的引例：函数 cc(n, k) 等于「不用第 k 种」加上「用一枚第 k 种之后再继续凑」——递推式 $cc(n,k) = cc(n,k-1) + cc(n-c_k,k)$ 与本讲完全背包计数完全一致（把 max 换成加号）。下面把同一递推式的三种实现并列运行，观察求出同一答案的代价差异。本演示采用简化面值 {1,5,10,25}（原书用 {50,25,10,5,1}）。递推式与算法完全一致，仅最终方案数随面值集合而异：对 target=100，五面值 {50,25,10,5,1} 方案数为 292，简化四面值 {1,5,10,25} 为 242。

调用次数 ≠ 实际耗时。把目标金额拖到 60 并运行，会看到 memo 调用次数(~176)反而少于 DP 状态更新次数(~203)，但耗时仍是 DP 的几倍——memo 一次调用要拼字符串键 + hash 查找 + 压栈出栈（≈30 单位）,DP 一次更新只是两次数组读 + 加法 + 写（≈3 单位）。两者算法层都是 $O(NV)$ ，但常数因子相差近一个数量级（memo 总成本 ≈ 176×30 = 5280,DP ≈ 203×3 = 609）。这还没算 DP 的更深层优势：其一，无递归栈，不存在栈溢出风险；其二，可滚动压缩到 $O(V)$ 空间（本讲 §2 已示）；其三，DP 沿 $F[v]$ 连续递增访问数组，访存局部性好、对 CPU cache 友好，而 memo 的 hash 查找是随机访存，cache 命中率低。

NOTES · memo 反超的情形 · 稀疏状态空间

DP 的弱点是「无论用得到与否，整张表都要填一遍」。当状态空间稀疏(大多数 (amount, kinds) 不会被访问),memo 的「按需触发」就能跑赢 DP 的「填遍整张表」。

案例	参数	memo 触及	DP 填表	优势
稠密（本演示）	target=60, {1,5,10,25}	~180	203	同阶 → DP 胜在常数
稀疏	target=600, {100,200,500}	~25	1003	memo 快约 40 倍
非矩形	状态空间是树/图（第 7 讲）	按需	——	DP「全表填充」不再适用

稀疏案例可手算：面值 {100,200,500} 下任何 amount 都只能是 100 的倍数，memo 实际写入的 (amount, kinds) 仅 12 个，加上若干命中与基底返回约 25 次；而 DP 不论可达与否把 v∈[cᵢ,600] 全扫一遍，合计 501+401+101=1003 次更新，绝大多数填的是 0。

NOTES · 关键概念出处 · SICP 与凑零钱

完全背包(unbounded knapsack)是经典 NP-hard 整数规划在小整数容量下可由 DP 求解的实例，详见 Kellerer, Pferschy, Pisinger, Knapsack Problems(Springer, 2004)第 8 章。凑零钱(coin change)最著名的引用来自 SICP(Abelson & Sussman, 1985)§1.2.2：书中以未记忆化的树递归呈现，作为 tree recursion 低效性的反面引例；§3.3.3 才介绍 memoization。

在工程中，凑零钱算法是支付与货币系统的核心模块——ATM 现金分配、POS 找零、自助柜员机面值规划均会用到本节方法或其近似变体。

6 · 凑零钱（二）· 最少硬币数

§4 把完全背包的 max 聚合换成求和得到「方案数」变形；本节把它换成 min，得到完全背包族的第三种聚合形式——「恰好凑出指定金额所需的最少硬币数」。 $F[v]$ = 恰好凑出金额 v 所需的最少硬币数（不可达则 $+\infty$ ）；初值 F[0]=0、 $F[1..V]=+\infty$ ；转移 $F[v] = \min (F[v], F[v-C_i]+1)$ ，对每种面值递增遍历 $v\in [C_i,V]$ 。

无解情形:V=7、coins={2,4} 时 $F[7]=+\infty$ ——任何 {2,4} 的非负组合都凑不出奇数。这是 $+\infty$ 初值的实战意义：同一份代码，既给出最优解，也清晰报告「不可凑出」。

NOTES · 关于贪心 · 正则币制与失效反例

用人民币 {1,2,5,10} 元凑 17 元——「10+5+2=17，共 3 枚」正是贪心策略（每次取不超过剩余金额的最大面值），而且确实是最少枚数。这种「贪心就够用」的直觉对中文读者是正确的——但不是因为贪心本身普适，而是人民币面值是精心设计过的：满足「贪心在所有金额上都达到最少枚数」的面值集合称为正则币制(canonical coinage)。美式 {1,5,10,25} 美分、人民币 {1,2,5,10} 元都是实例。

一旦币制不正则，贪心立刻失效。{1,3,4} 是最简反例，在 V=6 即暴露：贪心 6→4（剩2）→1→1 共 3 枚；最优 6=3+3 共 2 枚。这种失败模式在工程中常见：满减券组合（如 {30,50,80,200}）、商品按 {3,5,7} 装箱、游戏代币、历史货币、邮资面值——都可能不正则，「最少件数」决策不能套贪心，必须 DP。

正则性本身可在多项式时间判定。给定面值集合是否正则，存在可判定准则：Pearson 给出多项式时间算法(D. Pearson, A polynomial-time algorithm for the change-making problem, Cornell ORIE TR 94-9, 1994；载于 Operations Research Letters 33(3), 2005),Cai(2009)在此基础上进一步降低复杂度。换言之「日常感觉对」不等于「一眼可判定」——正则与否本身就是需要专门算法回答的命题。

聚合算子 → 问法对照：同一份完全背包骨架，只换聚合算子即应对不同问法。

聚合算子	初值约定	问法	本讲位置
max	F[0..V]=0	最大价值	§1-§3 主线
+（求和）	F[0]=1，其余 0	方案数（组合/排列）	§4
min	F[0]=0，其余 +∞	最少件数	§5（本节）

每种聚合算子对应自己的初值约定——这是「问法变化」的核心抽象，第 9 讲会把它系统化为统一框架。

7 · 应用案例 · 同种券反复使用

把完全背包应用于电商场景：平台对若干种满减券开放无限领取（常见于双 11、618 的「天天可领」）——用户面对同一种券可反复使用任意张。把购物车总额视为容量 V、券门槛视为费用 C、单张减免视为价值 W，求最大总减免即标准完全背包。调整购物车总额，观察 DP 如何在性价比最高的券与可填补零头的小券之间权衡。

同一种券被反复选取，直观反映完全背包「v 递增循环」的语义。把总额从 ¥50 调至 ¥600 可观察：性价比最高的满 80-22 在容量充裕时连续出现，而 ¥60 这种较小容量下 DP 会改选门槛更低的满 30-6，利用率（已用门槛/总额）接近 100%。

「每种 SKU 可任意件进货、资金 V 下最大化毛利」的批发场景，在引入起订量与库存上限后变为多重背包（见第 3 讲）。

8 · 延伸阅读

本章提供两类拓展：一是把本讲若干变形与经典文献(SICP / Concrete Mathematics)关联指明；二是为第 3 讲（多重背包）的核心技术——二进制拆分——预先讲清动机、论证与最小示例。

8.1 · 一 · 凑零钱方案数与生成函数

「凑零钱方案数」在外层枚举顺序上的差异（组合 vs 排列），与序列计数中的 ordered / unordered partition 对应，详见 Concrete Mathematics(Graham, Knuth, Patashnik, 1994)第 7.5 节关于 generating function 的讨论。完全背包的等价方程亦可视为一类带状态的递推关系，与有限自动机理论存在联系。

8.2 · 二 · 前瞻 · 通向多重背包的二进制拆分

第 3 讲（多重背包）的核心技术——二进制拆分——值得读完本讲后预先理解。完全背包本身虽不需要它（递增循环已是 $O(NV)$ ），但其极限情形（把无限件视为 M 件 01 物品）恰是它能介入的场景：遇到题面写 $M=10^9$ 但 $V\cdot \log M$ 仍可控的「完全背包」，直接套二进制拆分即可。

问题的根：从多件枚举到 01 决策。每种物品至多取 M 件。朴素做法枚举取的件数 k∈{0,1,…,M}，单种 $O(M)$ 次，总 $O(NVM)$ 。关键改写：找一组打包好的「物品包」，每个 once-or-none（转化为 01 背包），使任意 $k\in [0,M]$ 都能由某些包的子集精确表达——若用约 log M 个包覆盖 [0,M]，复杂度降到 $O(NV\cdot \log M)$ 。

为什么是 2 的幂。把原物品 (C,W) 拆成大小 ${1,2,4,\dots ,2^(t-1)}$ 的若干包，加一个余数包 r，满足 ${1+2+4+\dots +2^(t-1)+r=M}$ 。对任意 $k\in [0,M]$ 都能找到子集和恰为 k——证明即二进制表示。

三进制为什么不行。三进制包 {1,3,9,…} 下要表示 k=2 必须取两个 1 包——退化回「多次选择」，01 性质被破坏。结论：在「等比包覆盖 [0,M] 且每包 once-or-none」目标下，二进制是最常用且最简洁的选择。其他覆盖集合（如 {1,2,3,7}）亦可达到 log M 量级，但需要更精细的构造证明；「二进制拆分」中的「二进制」是由 once-or-none(01)约束反推而出，而非凭空选定。

最小示例 · M=13。从 1 翻倍直到累加超过 M: ${1+2+4=7\le 13}$ ，但 1+2+4+8=15>13，停在 {1,2,4}，余数 $r=13-7=6$ 。最终包集合 {1,2,4,6}——共 4 件 once-or-none 包，而非朴素的 14 个 k 选项。每个包在 01 背包里费用 $C\cdot 包大小$ 、价值 $W\cdot 包大小$ 。

8.3 · 通向第 3 讲 · 多重背包

第 3 讲将把「每种无限」放宽为「每种至多 Mᵢ 件」，得到多重背包问题。届时朴素枚举复杂度为 $O(NV\cdot \bar{M})$ ，可通过二进制拆分降至 $O(NV\cdot \log \bar{M})$ ——本讲提及的「将单种物品拆为若干 01 物品」的思想将在此真正发挥作用。单种物品拆出的总件数为 $\lceil \log _2(M+1)\rceil$ ，覆盖性手算与边界 M 行为亦在第 3 讲展开。