01 背包：每件至多选一次

NOTES · 2ᴺ 的爆炸增长 · 朴素方案为何不可扩展

把 ${2^N}$ 代入具体数字，即可看清指数增长的「墙」。下表按每秒 ${10^8}$ 次基本运算估算耗时：

增长是逐件翻倍：每多一件物品，工作量乘 2。N 从 30 到 40 仅增 10 件，耗时却从 10 秒跳到 3 小时。朴素枚举的正确性无可争议——它确实给出最优解；失败的不是「对不对」，而是「算不算得完」。后续 §3 贪心牺牲正确性换速度，§4 的 DP 则保留正确性、换一种方式枚举：把决策树的重叠子问题记忆化，把 $O(2^N)$ 个节点缩减到 $O(NV)$ 个 (i, v)。

NOTES · 复杂度谱系 · 伪多项式 · NP-hard 与 FPTAS

常有疑问：$O(NV)$ 是否已是最优？严格而言并非如此——01 背包属 NP-hard 问题，但就实际可用而言已经够好。把它放进算法谱系对比即可看清各方案的取舍：

伪多项式(pseudo-polynomial)。$O(NV)$ 对容量 V 是线性的，但 V 在输入中以 log V 个比特表示：若 V 为 32 位整数，最坏情形 $O(N\cdot 2^{32})$ 便不再是多项式。这正是 01 背包仍属 NP-hard 的根本原因——不存在对输入位长多项式的精确算法（除非 P = NP）。工程中 V 通常是较小整数（几千到几百万）,$O(NV)$ 远低于可等待的极限，故称「够好」。需要对大 V 给出可控误差的近似时，可用 FPTAS，以 $O(N^3/\varepsilon )$ 换取 $(1-\varepsilon )$ 近似比。

NOTES · 二维表的完整推演 · V=8、4 件物品

取 V=8、四件物品 (C,W) = (2,3), (3,4), (4,5), (5,6)（即上方演示的默认数据），逐行算出 $F[i][v]$:

单元读法举例：F[3][6]=8 表示「在物品 1..3 中选取、费用不超过 6 时的最大价值为 8」。其来源为 $\max (F[2][6], F[2][2]+W_3) = \max (7, 3+5) = 8$，即选取了第 3 件。最终答案 F[4][8]=10，对应方案为选第 2、第 4 件（费用 3+5=8、价值 4+6=10）。

回溯具体方案——从 $F[N][V]$ 出发，对每个 i（自 N 递减至 1）：若 $F[i][v]=F[i-1][v]$ 则第 i 件未选、v 不变；否则第 i 件选取、v 减去 $C_i$。对照上表逐步执行：

起点 (i,v) = (4,8):
  F[4][8]=10, F[3][8]=9    10 ≠ 9   → 第 4 件选取, v ← 8 − 5 = 3
  F[3][3]=4,  F[2][3]=4     4 = 4   → 第 3 件未选,     v = 3
  F[2][3]=4,  F[1][3]=3     4 ≠ 3   → 第 2 件选取, v ← 3 − 3 = 0
  F[1][0]=0,  F[0][0]=0     0 = 0   → 第 1 件未选
终止: 选第 2、第 4 件,总费用 3+5=8,总价值 4+6=10 ✓

DP 在给出最优值的同时，可经这一回溯恢复具体最优解——这是它相较贪心（不保留状态空间）与 §5 一维压缩（覆盖式更新丢弃历史）的优势。tie-breaking 与多最优解的处理见下方「多最优解与 tie-breaking」NOTES。

NOTES · 自顶向下记忆化的等价实现

Listing 4.1 采用自底向上填表：从 $F[0][\cdot ]$ 逐行算到 $F[N][V]$。同一递推可改写为自顶向下递归 + 记忆化的等价形式——即把 §2 提到的「${2^N}$ 决策树的重叠子问题记忆化」直接实现：从 $F[N][V]$ 出发，需要哪个子问题就递归求解，首次算出后存入 memo，后续直接读取。两者求解同一函数 $F[i][v]$、用同一递推，总计算次数同为 $O(NV)$，差异在于：自底向上按 (i,v) 字典序遍历整张表，可滚动压缩到 $O(V)$（见 §5）；自顶向下只触及实际用到的子问题，但需 $O(NV)$ 的 memo 表加 $O(N)$ 递归栈，无法同样压缩。状态空间稀疏时记忆化递归常数更优，稠密（如本题）时填表更快且无栈溢出风险。记忆化递归 / 自底向上 DP / 朴素树递归三者的调用次数对比，见 第 2 讲的 SICP 换零钱演示。

NOTES · 前缀与后缀：两种等价的状态对偶

本讲的 $F[i][v]$ 取前缀视角:i 是「在物品 1..i 中选取」的候选集合上界。读者偶有把「前 i 件」误读为「剩余未判定的 i 件」，后者对应等价的后缀状态 $G[j][v]$ =「从第 j 件到第 N 件中选取、费用不超过 v 的最大价值」，边界 G[N+1][v]=0，答案为 $G[1][V]$。两种定义在算法上完全等价，本讲采用前缀。须强调：「前缀 / 后缀」刻画的是候选物品集合的形状，与「一维空间压缩」一节讨论的循环方向（递增 / 递减）是两件不同的事，不要混淆。

NOTES · 多最优解与 tie-breaking

回溯时，若某步同时满足 $F[i][v]=F[i-1][v]$ 与 $F[i][v]=F[i-1][v-C_i]+W_i$，本讲按「未选」分支返回——这只是一种任意的 tie-breaking 约定。达到同一最优值 $F[N][V]$ 的物品子集可能不止一个；如何枚举或计数全部最优方案，见 第 9 讲（问法变化）的「最优方案总数」，那里把「任选一条」升级为「对每条相等分支累加」的计数语义。

NOTES · 关键概念出处

动态规划这一方法论由 Richard Bellman 于 1950 年代提出，其奠基著作 Dynamic Programming(Princeton University Press, 1957)系统确立了「最优子结构」与「重叠子问题」的框架。01 背包作为整数规划的经典实例，其 $O(NV)$ 算法在 1960 年代起由 Gilmore 与 Gomory 在切割下料(cutting-stock)问题的线性规划途径中系统讨论(Operations Research, 9(6), 1961)。现代算法教材均设专章介绍，如 CLRS · Introduction to Algorithms。就背包族的系统综述而言，见 Kellerer, Pferschy & Pisinger · Knapsack Problems(Springer, 2004)——该书亦明确：背包问题（就其一般化形式）是 NP-hard 的典型代表，而伪多项式算法对小整数容量足够实用。

NOTES · 循环方向反例 · 单件 (C,W)=(2,3)、V=4

用最小规模把「为何必须递减」逐步看清：仅一件物品 (C,W)=(2,3)、容量 V=4。因每件至多选一次，正确解为 F[4]=3。两个方向的 trace 对照：

递减方向（正确）:

v=4: F[4] = max(F[4], F[2]+3) = max(0, 0+3) = 3
v=3: F[3] = max(F[3], F[1]+3) = 3
v=2: F[2] = max(F[2], F[0]+3) = 3
最终 F[4] = 3 ✓

递增方向（错误，退化为完全背包）:

v=2: F[2] = max(F[2], F[0]+3) = 3
v=3: F[3] = max(F[3], F[1]+3) = 3
v=4: F[4] = max(F[4], F[2]+3) = max(0, 3+3) = 6  ← 该物品被选取两次

关键在第三步：递减时读 $F[2]$ 仍是「未处理本件」的旧值 0（等价于二维的 $F[i-1][2]$），故每件至多一次；递增时 $F[2]$ 已在本轮被改写成 3（等价于 $F[i][2]$），于是 $F[4]$ 把同一件物品又算了一遍 → 6。这「同件可反复选」恰是完全背包的语义，见 第 2 讲。

NOTES · 一维压缩的代价 · 失去回溯路径

一维 F 数组只保留「已处理物品 1..i 后的最优价值」，每一轮原地覆盖上一轮的全部内容——拿到 $F[V]$ 后无法再回推「哪些物品被选取」，这与 §4 二维表逐行保留历史、可从 $F[N][V]$ 反查的能力恰成对照。若题目同时要求最优值与具体方案，有两条补救：

其一，保留完整的二维表 $F[i][v]$ 用于回溯，即放弃空间压缩、退回 §4 的二维实现。其二，在一维 DP 之外另开一张 $N\times V$ 的「决策来源」位图，每次更新时记录「本格是否选取了第 i 件」，事后据此重建方案——存储仍为 $O(NV)$，但相较保留整张数值表，常数更小。

NOTES · 两类退化边界 · 由循环范围自然吸收

物品费用全超过容量。取 V=3、物品 (C5,W100)、(C4,W80)，任一物品费用均大于 V，不存在可行选取，结果 F[3]=0（什么都不选）。实现无需特判：内层循环 for (v = V; v >= Cᵢ; v--) 在 $V < C_i$ 时自动为空，边界由循环范围隐式吸收。

物品集为空(N=0)。对称的另一退化是外层 for (const {C,W} of items) 一次也不执行，F 在初始化后即为最终结果（一维约定下 F[0..V]=0，对应「无物品可选，任意容量最大价值均为 0」）。两类边界同理——皆由循环范围自然处理，实现层面无需任何特判。这种「边界被循环自然吸收」是 DP 实现的一个隐性优势，后续各讲也将反复利用。