代码与动画 0/1 KNAPSACK
0/1 背包.
在容量限制下，每件物品最多选择一次，逐格比较选与不选的价值。
时间 O(nC)空间 O(nC)二维 DP 与选择回溯
原理与执行逻辑
以“前 i 件物品、容量 c”定义子问题。当前物品只能选一次，比较不选它的价值与从上一行扣除重量后再加上它价值的方案。
执行步骤
- 建立二维 dp，空物品行初始化为 0。
- 不选当前物品时取 dp[i - 1][c]。
- 容量允许时，选择价值为 dp[i - 1][c - weight] + value，写入两者最大值。
- 从最终状态向前比较行间价值，回溯选中物品并扣减剩余容量。
关键理解
两个候选都来自上一行，确保当前物品不会重复使用。dp 表示容量不超过 c 的最大价值；回溯相同价值时保留不选方案。
简短示例
重量 [2, 3]、价值 [3, 4]、容量 5 时，选择第二件可接续容量 2 的上一行价值 3，总价值为 7。
代码与执行动画
STEP 0 / 61function knapsack(weights, values, capacity) { const n = weights.length; const dp = Array.from({length: n + 1}, () => Array(capacity + 1).fill(0)); for (let i = 1; i <= n; i++) { for (let c = 0; c <= capacity; c++) { const skip = dp[i - 1][c]; const take = c >= weights[i - 1] ? dp[i - 1][c - weights[i - 1]] + values[i - 1] : -Infinity; dp[i][c] = Math.max(skip, take); } } const selected = []; let c = capacity; for (let i = n; i > 0; i--) { if (dp[i][c] > dp[i - 1][c]) { selected.push(i - 1); c -= weights[i - 1]; } } return {value: dp[n][capacity], selected: selected.reverse()};}当前数据正在操作已访问 / 命中标记 / 指针
输出 / 辅助状态
物品0: 重2/值3物品1: 重3/值4物品2: 重4/值5物品3: 重5/值8
0
初始化背包表
行是已考虑的物品，列是容量。空物品行的价值为 0。
配置演示数据
应用后重新生成执行过程，可单步观察结果。
0/1 背包的操作规则
行表示已考虑的物品数，列表示容量。依赖上一行以保证物品只使用一次；相同价值时保留不选方案，最终回溯选中物品。
对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
- 对应题目416. 分割等和子集打开题目
将元素视为只能选一次的物品，判断是否能达到总和的一半；状态由最大价值调整为可达性。
- 扩展练习474. 一和零打开题目
扩展到两个容量限制的 0/1 背包。