0-1 背包

动态规划 · 优化 / 取舍

装什么最值钱

有一个容量有限的背包和若干件物品，每件有重量和价值，每件要么整件装、要么不装（这就是「0-1」）。在不超重的前提下，怎么装总价值最大？这是最经典的动态规划入门题——和「编辑距离」一样填一张表，但填的是「最大价值」而非「最少代价」。

取，还是不取

设 dp[i][w] = 只考虑前 i 件物品、背包容量为 w 时能装出的最大价值。边界：没有物品（第 0 行）或容量为 0（第 0 列），价值都是 0。对第 i 件物品，只有两种选择：

装不下（它的重量 > 当前容量 w）——只能不取，dp[i][w] 直接沿用上一行dp[i-1][w]；装得下——在不取（dp[i-1][w]）和取（dp[i-1][w-重量] + 价值，即腾出重量后的最优再加上本物品）之间取较大者。

下面固定 4 件物品 A(重2,值3) B(重3,值4) C(重4,值5) D(重5,值6)、容量 5。点「下一步」逐格看：当前格琥珀环，它参考的「不取」上格和「取」的左上偏移格都黄色高亮——填入即变绿。走到底，右下角 = 7（选 A+B：重 2+3=5、值 3+4=7）。右侧代码随每一步同步高亮。

	1	2	3	4	5
∅	0	0	0	0	0
A
B
C
D

边界：没有物品（第 0 行）或容量为 0（第 0 列）时，最大价值都是 0

1function knapsack(w: number[], v: number[], W: number): number {
const m = w.length;
const dp = Array.from({ length: m + 1 }, () => Array(W + 1).fill(0));
for (let i = 1; i <= m; i++) {
  for (let c = 1; c <= W; c++) {
    if (w[i - 1] > c) {
      dp[i][c] = dp[i - 1][c];
    } else {
      dp[i][c] = Math.max(
        dp[i - 1][c], dp[i - 1][c - w[i - 1]] + v[i - 1]);
    }
  }
}
return dp[m][W];
15}

容量5

物品A(重2,值3) B(重3,值4) C(重4,值5) D(重5,值6)

1 / 22

每格只看上一行的两个格子就能定，共 O(物品数 × 容量) 格，远快于枚举 2ⁿ 种取法。这正是动态规划：把「前 i 件、容量 w」的子问题解存进表，后面的直接查表复用。递推里的「取 / 不取」两个来源，就是把「选择」显式地摆在两个邻居格上。

0-1 背包在哪里用

资源分配：预算/时间有限，选收益最大的项目组合。
装载 / 切割：容器装货、原料下料求最优。
DP 基石：完全背包、多重背包、子集和都由它变体而来。它和编辑距离分别是优化型与序列对齐型二维 DP 的代表。

想看另一种「填表」DP（求最少代价而非最大价值），回看 编辑距离——两页对照，能体会动态规划「定义状态 + 写对递推 + 逐格填表」的通用套路。

算法可视化

0-1 背包

装什么最值钱

取，还是不取

0-1 背包在哪里用