0/1 背包

0/1 背包在容量限制下选择物品，每件只能取一次或不取。动态规划保存每个物品前缀、每种容量的最大价值，时间 O(n × capacity)。本课使用正整数重量与整数容量。

决定是否取第 i 件物品时，只能读取上一行，它代表“还没有这件物品”的问题。这个规则避免同一物品被重复装入。

0/1 背包如何工作

dp[i][w] 表示只使用前 i 件物品、容量 w 时的最大价值。无物品的第 0 行为 0；正重量模型下，第 0 列也为 0。

逐行、从左向右填容量。当前物品过重，只能取 skip = dp[i - 1][w]。放得下时，还可取：

take = value + dp[i - 1][w - weight]

两者取较大值。重点是两项都读第 i - 1 行。若 take 读本行，当前物品就可能被再次使用，变为完全背包的规则。

填完后从 dp[n][capacity] 逆向回溯。值与上方相同，按本课平局规则跳过物品；不同则取该物品，容量减去其重量，并退到上一行。

逐步演示

默认容量 9：

1. 初始化基础行和列为 0，后续递推最终依赖它们。
2. A：容量 1 放不下，复制 0。容量 2 读取 dp[0][0]，不是 dp[1][0]，得到 3。整行为 0, 0, 3, 3, 3, 3, 3, 3, 3, 3。
3. B：容量 1、2 复制上一行；容量 3 取 B 得 4。容量 5 读取 dp[1][2] = 3，B+A 得 4 + 3 = 7；到容量 9 都保持 7。
4. C：容量 4 得 8，容量 6 的 C+A 得 11，容量 7 的 C+B 得 12，容量 9 加上上一行容量 5 的最优值得 15。
5. D：价值也为 8，但重 5。容量 6 比较 skip = 11、take = 8，跳过。容量 8 两者都为 12，按规则跳过。容量 9 得 8 + dp[3][4] = 8 + 8 = 16，取 D 获胜。
6. E：单件价值最高 10，在容量 8 把值改为 13，但容量 9 仍不如旧值 16。最大单件价值不保证最佳组合。
7. 回溯：从 dp[5][9] = 16 开始，与上方相同，跳过 E；取 D，容量 9→4；取 C，容量 4→0；B、A 跳过。选择 C+D，总重量 9、总价值 16。

时间与空间复杂度

该界依赖容量的数值大小，属于伪多项式时间，不能只按容量的二进制输入位数理解。

边界情况

• 容量 0，返回 0，不选择物品。
• 当前物品超过容量，只能复制上一行。
• 全部物品都放不下，答案为 0。
• 恰好放下时，take 的剩余容量来源是第 0 列。
• 平局需一致规则。本课优先 skip，使回溯结果可复现。

常见错误

• 读取 dp[i][w - weight]。 会重复使用当前物品，不再是 0/1 规则。
• 按绝对价值贪心。 greedy-trap 中，贪心取 A 得 30，DP 取 B+C 得 56。这个反例针对绝对价值，不是价值重量比；B、C 的比值本来更好。
• 缺基础行列。 会让第一件物品和零容量依赖变成散布的特殊分支。
• 正向追物品集合。 应从最终格向后，逐行比较上方。
• 混合单位。 重量与容量同单位，价值是另一项评分。价值不能加到重量上。

简化范围

二维表用来展示上一行依赖。只求最优值时可压缩成一行，但容量必须从大到小更新，防止本轮复用当前物品。需要恢复物品集合时还需保留相应信息。小整数重量和少量物品只是显示范围，同一递推也适用于更大实例。