15.2.8 背包问题（动态规划法）

动态规划解决 0-1 背包的关键是把“选哪些物品”转化为一张状态表：前 $i$ 个物品，在容量为 $t$ 的背包中，最多能获得多少价值。每个状态只依赖规模更小的状态，因此可以查表或递归记忆化。

状态定义

定义：

$$C(i,t)=\text{前 }i\text{ 个物品放入容量为 }t\text{ 的背包时可获得的最大价值}$$

这里的 $i$ 表示只考虑前 $i$ 个物品，$t$ 表示当前容量限制。答案就是 $C(n,W)$。

符号	含义
$v_i$	第 $i$ 个物品价值
$w_i$	第 $i$ 个物品重量
$W$	背包总容量
$C(i,t)$	前 $i$ 件物品、容量 $t$ 下的最大价值

递推式：放不下、放或不放

动态规划的代码填空几乎都来自递推式。

$$C(i,t)=\{\begin{array}{ll}0,& i=0\text{ 或 }t=0\\ C(i-1,t),& t<w_i\\ max\{C(i-1,t),C(i-1,t-w_i)+v_i\},& t\ge w_i\end{array}$$

三种情况要逐一理解：

情况	含义	代码思路
$i=0$ 或 $t=0$	没物品或没容量，价值为 0	C[i][t] = 0
$t<w_i$	第 $i$ 件太重，放不下	C[i][t] = C[i-1][t]
$t\ge w_i$	第 $i$ 件可以尝试放入	比较“不放”和“放”

“不放第 $i$ 件”时，价值是 $C(i-1,t)$；“放第 $i$ 件”时，剩余容量为 $t-w_i$，前面只能从前 $i-1$ 件中选，所以价值是 $C(i-1,t-w_i)+v_i$。

最优子结构与重叠子问题

0-1 背包适合动态规划，是因为它同时具备两个特征：

• 最优子结构：若最优解包含第 $i$ 件物品，则剩余部分必须是“前 $i-1$ 件物品、容量 $t-w_i$”的最优解；若不包含第 $i$ 件，则答案来自“前 $i-1$ 件、容量 $t$”。
• 重叠子问题：不同选择路径会反复计算同一个 $C(i,t)$，因此需要数组保存中间结果。

这也解释了为什么动态规划代码里会出现二维数组 C 或 dp。数组不是普通输入，而是保存中间最优值的表。

自顶向下与自底向上

实现方式	行为	代码特征	复杂度直觉
自顶向下	从 $C(n,W)$ 开始递归求小状态	函数递归、数组初值如 -1 表示未计算	有记忆化时避免重复；无记忆化会很大
自底向上	从 $C(0,0)$ 等小状态开始填表	双层循环遍历物品和容量	通常 $O(nW)$

字幕里的真题代码使用了类似自顶向下的写法：如果 C[i][j] != -1，说明这个状态已经算过，直接返回；否则按递推式计算并存入 C[i][j]。

代码填空如何从递推式翻译

假设函数 maxValue(v, w, i, j) 表示 $C(i,j)$，二维数组 C[i][j] 保存结果。

代码空	对应含义	典型填法
已计算状态直接返回	C[i][j] != -1 时不用重复算	return C[i][j];
边界条件	没物品或没容量	C[i][j] = 0;
能否放第 i 件	容量不小于当前重量	j >= w[i] 或按题目下标写 j >= w[i-1]
放第 i 件的价值	剩余容量加当前价值	maxValue(v,w,i-1,j-w[i]) + v[i]
取较大者	比较放与不放	if (temp > C[i][j]) C[i][j] = temp;

下标是最容易出错的地方。如果题干物品编号从 1 开始，公式里的 $w_i$ 对应 w[i]；如果 C 数组从 0 开始，常会写成 w[i-1]、v[i-1]。考试要跟随题干代码，不要机械套模板。

小例子：为什么比较两种方案

假设当前考虑第 $i$ 件，容量为 $t$。如果放它，价值增加 $v_i$，但容量减少 $w_i$；如果不放，容量保持 $t$，但不能得到 $v_i$。

flowchart TD
  A["状态 C(i,t)"] --> B["不选第 i 件: C(i-1,t)"]
  A --> C["选第 i 件: C(i-1,t-w_i)+v_i"]
  B --> D["取较大值"]
  C --> D

这就是动态规划比单纯贪心可靠的地方：它不是只看当前物品“看起来值不值”，而是比较两个子问题的最优结果。

实例题的处理方式

字幕里提到，若题目给五件物品、容量为 11，要求最大价值，直接手填完整二维表可能很繁琐。考试中可以结合方案列举和容量约束快速判断，但写代码填空时仍然要回到递推式。

对于实例运行结果题，建议：

1. 先看容量是否较小，能否列举可行组合。
2. 按价值较大的物品开始尝试，但不要把这当成贪心证明。
3. 每个候选方案都检查总重量是否超过容量。
4. 在可行方案中比较总价值。

动态规划与其他方法的取舍

方法	能否保证 0-1 背包最优	代价	适合考点
贪心	通常不能	快	策略判断、满意解
回溯	能，若完整搜索并正确剪枝	最坏 $O(2^n)$	解空间树、剪枝、回退
动态规划	能	常见 $O(nW)$ 时间和空间	递推式、状态表、代码填空

动态规划用空间换时间：二维数组保存中间结果，避免重复求同一个子问题。这就是它相对于朴素递归的技术迭代价值。

单选

0-1 背包中，当第 $i$ 件物品重量 $w_i$ 不超过当前容量 $t$ 时，正确的状态转移是哪一个？

AC(i,t)=C(i,t-w_i)+v_iBC(i,t)=C(i-1,t-w_i)CC(i,t)=max(C(i-1,t), C(i-1,t-w_i)+v_i)DC(i,t)=C(i-1,t)+v_i

本节小结

动态规划法用状态表表达 0-1 背包的最优子结构。代码填空最重要的是把递推式翻译成数组访问：容量不足只能不选，容量足够就比较选与不选，已经计算过的状态直接返回。