0/1 背包

0/1 背包是动态规划入门必学。给定 N 件物品（每件有重量 w 和价值 v），背包容量 W，每件物品要么拿要么不拿，问最多能装多少价值。

状态定义

dp[i][j] = 只用前 i 件物品、背包容量是 j 时，能装的最大价值

边界：dp[0][j] = 0（一件都不选时价值是 0）。

转移方程

对每件物品 i（重量 wᵢ，价值 vᵢ），考虑容量 j 时有两个选择：

• 不选：dp[i][j] = dp[i-1][j]
• 选（前提是 j ≥ wᵢ，装得下）：dp[i][j] = dp[i-1][j - wᵢ] + vᵢ

取两者最大值：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - wᵢ] + vᵢ)

最终答案是 dp[N][W]。

反推方案

知道最大价值还不够，往往要知道选了哪些物品。从 dp[n][W] 倒着看：

• 如果 dp[i][w] != dp[i-1][w] —— 说明第 i 件被选了，回退到 dp[i-1][w - wᵢ]
• 否则第 i 件没选，回退到 dp[i-1][w]

滚动数组优化

观察到 dp[i] 只依赖 dp[i-1]，可以把二维数组压成一维：

for (int i = 1; i <= n; ++i)
  for (int j = W; j >= w[i-1]; --j)  // 注意倒序！
    dp[j] = max(dp[j], dp[j - w[i-1]] + v[i-1]);

为什么 j 要倒序？ 因为 dp[j - wᵢ] 必须是**上一轮（不含第 i 件）**的值。如果正序，dp[j - wᵢ] 已经被本轮覆盖（含了第 i 件），就变成可以重复选了 —— 那是完全背包。

复杂度

• 时间：O(n·W)
• 空间：O(n·W) 二维 / O(W) 滚动数组

在动画里看什么

• 顶上一排是物品列表（高亮当前正在处理的）
• 二维表格行 = 物品序号 i，列 = 容量 j
• 深蓝单元格：当前正在算的 dp[i][j]
• 箭头：当前格从哪两个上格子选择 —— 实线红色 = “选了第 i 件”，虚线灰色 = “没选”
• 最右下角 dp[N][W] 是最终答案
• 完成时暖红高亮的物品就是反推出来的最优方案