对于01背包的一些疑问

一、二维 DP 的初始化：到底在初始化什么？

1) 状态回顾

令 dp[i][c] 表示：只用前 i 件物品、容量限制为 c 时，能得到的最大价值。

2) 边界（base cases）

• dp[0][c] = 0：没有物品可选，价值只能是 0（无论容量多大）。

• dp[i][0] = 0：容量为 0，装不了任何东西，价值为 0。

这俩边界把 DP 表四边中的两条边先钉住了。之后的递推：

dp[i][c] = max( dp[i-1][c],                     // 不选第 i 件dp[i-1][c - w[i]] + v[i] )      // 选第 i 件（前提：c >= w[i]）

就可以从左上角向右下角顺利填满整张表而不必担心越界。

✅ 直觉：
没有行 0（没有物品）和列 0（没有容量）的“地基”，你没法从 dp[i-1][…] 推到 dp[i][…]；初始化就是把这层地基先搭好。

3) “恰好装满”与“容量不超过”的初始化区别（延伸必备）

• 默认 0/1 背包是“容量不超过 W 即可”：
  dp[0][c]=0, dp[i][0]=0 就够了。

• 若题目要求“恰好装满容量 W”：
  需要把“不可达”状态设成负无穷：

  • dp[0][0] = 0（恰好装满 0 的唯一方法是啥也不选）

  • dp[0][c>0] = -INF（没有物品又要装满正容量，不可达）
    这样就不会误把“没装东西”当成“恰好装满”的解。

二、一维 DP 的初始化：为什么“只改一行 dp 就够了”？

1) 状态回顾

把二维压缩成一维后，dp[c] 表示：在当前处理到的物品范围内，容量为 c 的最大价值。
（更精确的不变量见下一节）

2) 初始化内容

• 容量不超过版：
  直接 vector<int> dp(W+1, 0); 即可。
  含义：在“还没处理任何物品”的初始状态下，各容量的最优值都是 0（啥也不拿）。

• 恰好装满版：

  • dp[0] = 0

  • dp[1..W] = -INF（不可达）
    目的是禁止“没装东西也算达成”的结果。

✅ 一维和二维在语义上完全一致；只是把“上一行”的信息覆盖到同一行数组里。初始化之所以更“简单”，是因为“没处理任何物品”时的最优值就是 0 或 -INF（看问题要求）。

三、为什么一维要倒序遍历容量？（这是 0/1 背包的灵魂）

1) 循环不变量（重要！）

当处理第 i 件物品时：

• 进入容量循环前，dp[c] 存的是“只用前 i-1 件物品、容量 c 的最优值”（上一行）。

• 更新容量 c 后（这次迭代的 c），dp[c] 变成了“用到前 i 件物品、容量 c 的最优值”（本行）。

要保证这个不变量，遍历容量必须从大到小（W → w[i]）。原因如下。

2) 正序会“偷用”本轮更新，导致重复选同一件（变成完全背包）

看转移：
dp[c] = max(dp[c], dp[c - w[i]] + v[i])

• 若你正序（c = w[i]..W）更新：

  • 当你更新到某个 c 时，dp[c - w[i]] 可能已经在同一轮被本件物品更新过了（即已经是“用到前 i 件”的值），这就等价于允许把第 i 件拿多次（完全背包的策略），和 0/1 的“每件只能拿一次”矛盾。

• 若你倒序（c = W..w[i]）更新：

  • 当你更新 dp[c] 时，右边用到的 dp[c - w[i]] 由于 c - w[i] < c，在本轮尚未被更新，仍是“只用前 i-1 件”的旧值，符合 0/1 语义。

✅ 一句话：倒序保证右侧的 dp[c - w[i]] 仍是“上一行”的值，不会把第 i 件物品用两次。

3) 一个“正序错解”的小反例

容量 W=5，只有一件物品 w=2, v=3。

• 正确答案：最多拿一次，最优值应为 3（不能拿两次）。

• 正序更新（错误）：

  • 初始 dp=[0,0,0,0,0,0]

  • c=2：dp[2]=max(0, dp[0]+3)=3

  • c=3：dp[3]=max(0, dp[1]+3)=3

  • c=4：这里错了：dp[4]=max(0, dp[2]+3)=max(0,3+3)=6
    你看，它把同一件物品“拿了两次”（先造出 dp[2]=3，马上又用它来算 dp[4]）。

• 倒序更新（正确）：

  • c=5：dp[5]=max(0, dp[3]+3)=3

  • c=4：dp[4]=max(0, dp[2]+3)=3（此时 dp[2] 仍是 0，没被当前轮更新过）

  • … 最终不会超过 3。

四、把一切串起来（模板）

1) 二维（易懂、便于恢复选品）

int knap01_2d(const vector<int>& w, const vector<int>& v, int W) {int n = (int)w.size();vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));for (int i = 1; i <= n; ++i) {for (int c = 0; c <= W; ++c) {dp[i][c] = dp[i - 1][c];                      // 不选if (c >= w[i - 1]) {dp[i][c] = max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1]); // 选}}}return dp[n][W];
}

• 初始化：dp[0][c]=0, dp[i][0]=0（容量不超过）。

• “恰好装满”版本：dp[0][0]=0, dp[0][c>0]=-INF。

2) 一维（面试常写，注意倒序）

int knap01_1d(const vector<int>& w, const vector<int>& v, int W) {vector<int> dp(W + 1, 0);                      // 容量不超过版for (int i = 0; i < (int)w.size(); ++i) {for (int c = W; c >= w[i]; --c) {          // 必须倒序dp[c] = max(dp[c], dp[c - w[i]] + v[i]);}}return dp[W];
}

• 初始化：dp[0..W]=0（容量不超过）。

• “恰好装满”版把初始化改为：dp[0]=0, dp[1..W]=-INF（保持倒序不变）。

五、最后的思维“锚点”（一眼看懂）

• 二维初始化：
  “没有物品/没有容量 → 价值为 0”，或“恰好装满 → 不可达设 -INF”。

• 一维初始化：
  “容量不超过 → dp 全 0”；“恰好装满 → dp[0]=0，其它 -INF”。

• 一维倒序：
  防止在同一轮里复用当前物品（否则就成完全背包）。
  倒序确保右边的 dp[c-w] 仍是“上一行”的值。

好问题！把这三件事一次讲清：

1. 二维 DP 的遍历顺序

2. 一维 DP 的遍历顺序（为什么一定要倒序容量）

3. “先遍历物品的重量还是价值？”（澄清下概念）

① 二维 0/1 背包：遍历顺序怎么选？

状态：dp[i][c] = 只用前 i 件物品、容量 c 的最大价值。
转移：

dp[i][c] = max(dp[i-1][c], dp[i-1][c - w[i]] + v[i])   (c >= w[i])

只依赖上一行（i-1 行）。因此：

• 推荐顺序（最常见、最清晰）
  外层遍历物品 i = 1..n，内层遍历容量 c = 0..W（或 0..W/W..0 都行）：

  for (int i = 1; i <= n; ++i)for (int c = 0; c <= W; ++c)dp[i][c] = max(dp[i-1][c], (c>=w[i]? dp[i-1][c-w[i]]+v[i] : dp[i][c]));
  

  因为我们只读 dp[i-1][*]，这一整行在进入 i 之前已经算完了，内层容量顺序不影响正确性。

• 其它等价顺序
  你也可以把容量放外层、物品放内层（例如 for c=0..W 外层，for i=1..n 内层）并保证整体按 i 从小到大推进，二维表里“上一行/其它列”的值都已经在更早的迭代被填好——二维因为保存了整张表，顺序很宽松。但这种写法可读性差、容易想不清依赖，面试/比赛一般不这么写。

初始化（二维）

• dp[0][c] = 0（没物品）

• dp[i][0] = 0（容量 0）

若题目是“恰好装满”，则要改为：dp[0][0]=0, dp[0][c>0]=-INF，表示“不可达”。

② 一维 0/1 背包：为什么必须倒序容量？

压缩后状态：dp[c] 表示“当前处理到第 i 件物品时、容量 c 的最大价值”。
转移（在处理第 i 件物品时）：

dp[c] = max(dp[c], dp[c - w[i]] + v[i])     (c >= w[i])

关键不变量
当更新第 i 件物品时，在进入容量循环之前，dp[*] 里存的是“只用前 i-1 件”的结果；
更新某个 c 之后，dp[c] 才变成“用到前 i 件”的结果。

要保持这个不变量，就必须倒序容量：for (int c = W; c >= w[i]; --c)。
这样在计算 dp[c] 时，右边用到的 dp[c - w[i]] 仍是**上一轮（前 i-1 件）**的旧值，不会把第 i 件物品重复使用。

如果正序容量（错误）会怎样？
来个反例：W=5，一件物品 (w=2,v=3)。
正序时更新到 c=4：dp[4] = max(dp[4], dp[2] + 3)，而 dp[2] 在同一轮前面已被本件物品更新为 3，于是得到 dp[4]=6，等价于同一件拿了两次（变成完全背包）。
所以 0/1 背包的一维优化必须外层物品、内层容量倒序。

一维写法（容量不超过版）：

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

初始化（一维）

• “容量不超过 W”：dp[0..W] = 0。

• “恰好装满 W”：dp[0] = 0; dp[1..W] = -INF。

③ “先遍历物品的重量还是价值？”——概念澄清

在 0/1 背包的 DP 里，我们并不“遍历价值”。循环的两个维度是：

• 物品（索引 i，对应一对 (w[i], v[i])），

• 容量（c，从 0..W 或 W..0）。

所谓“先遍历重量还是价值”的说法，通常是把“容量 c（与重量约束相关）”和“价值 v[i]（只是转移里用到的常数）”混淆了。正确的问法是“先遍历物品还是容量”。

结论汇总

• 二维：推荐“物品外层、容量内层”，容量顺序随意；有整张表，依赖好想。

• 一维：物品外层、容量内层且必须倒序，否则就会把同一件物品重复用，变成完全背包。

• 初始化按题意选择“容量不超过/恰好装满”的版本。