0-1背包一维DP：倒序遍历、先遍历物品与先遍历背包

0-1背包这个题，我给不同的人讲过不下十遍，几乎每一轮都会卡在同一个地方：二维数组写得清清楚楚，一看就懂，压成一维之后脑子就开始打结，尤其卡在那个倒序循环上——为什么背包容量一定要从大到小跑？我把它改成正序，跑出来的数居然也像模像样，甚至有时候还更大，看着更"优"。再往下问一层，为什么一维写法只能先遍历物品、不能先遍历背包容量，绝大多数人就答不上来了，只能背结论。这篇就把这件事从头到尾拆开讲：从二维dp怎么推出来，到一维滚动数组到底省掉了什么信息，再到倒序遍历的每一步实际读的是哪个"旧值"，最后把"先遍历背包"为什么必然出错用可复现的数据摆出来。看完之后你不需要再背任何结论，0-1背包问题、一维dp数组、倒序遍历背包、先遍历背包、先遍历物品这几件事会连成一条完整的因果链。

1. 从题目到模型：0-1背包到底在问什么

1.1 三个约束条件先摆清楚

0-1背包的标准描述是：给定 n 件物品，第 i 件物品的重量是w[i]、价值是v[i]，再给一个承重上限为V的背包，问在总重量不超过V的前提下，能装走的最大总价值是多少。

这段话里有三个不能含糊的约束，我在看别人的代码时经常发现有人只记住了第一个：

• 每件物品最多取一次，取就是 1，不取就是 0，这正是"0-1"这个名字的来源，也是它和完全背包、多重背包最根本的分界线。
• 背包的重量上限是V，累计重量不能超，但不要求装满，装到 3.7kg 和装到 4.0kg 在"最大价值"这个目标下没有区别。
• 目标是总价值最大，不是重量最大，也不是物品个数最多。

这三条看着平淡，实际决定了后面所有代码细节。比如第二条直接决定了初始化怎么写——不要求装满时dp数组全填 0 就行；如果题目改成"恰好装满背包时的最大价值"，那初始化就必须是dp[0] = 0、其余位置填负无穷，否则你会得到一个"没装满但价值很大"的错误答案。很多人栽在这上面，把一道恰好装满的题按不要求装满写了，样例还过了，因为样例恰好就是能装满的。

1.2 暴力搜索为什么扛不住

最直觉的做法是枚举每件物品选或不选，一共 2^n 种组合，逐个检查重量、记录最大价值。n 等于 20 的时候是 100 万种组合，还能忍；n 等于 30 就是 10 亿，基本没戏。而真实的业务场景里 n 到几百、上千是常态，比如资源调度里"从一堆任务里挑哪些执行能产出最大收益"，候选集合动辄上千，2^n 这种量级连想都不用想。

更要命的是，这 2^n 种组合里有大量重复的子结构。举个具体例子：三件物品，重量分别是 1、2、3，价值分别是 10、20、30。组合"选物品1和物品3"和组合"选物品2……"在重量维度上经常撞到同一个剩余容量，后面能做的决策完全一样，但暴力搜索会把这些子问题重新算一遍又一遍。这就是典型的"重叠子问题"，也正是动态规划要切进去的地方。

1.3 为什么贪心在这里会翻车

有人会想，那我按"性价比"排序，优先拿价值密度最高的不就行了？不行。举个反例：V = 4，物品 A 重量 3、价值 30（密度 10），物品 B 和 C 重量都是 2、价值各 19（密度 9.5）。贪心先拿 A，占了 3kg，剩 1kg 什么都放不下，总价值 30。而最优解是拿 B 和 C，重量 4，价值 38。贪心在每一步局部看起来都对，合起来就错了，因为背包问题里"装不满的零头"会直接吃掉后面的机会。这就是为什么必须用动态规划，把"剩余容量"这个维度的所有可能性都考虑进去。

0-1背包是典型的 NPC 问题，但它有一个非常好的性质：重量维度是整数且上界有限。只要V不是天文数字，我们就能把"容量"作为状态维度展开，把指数级的组合搜索压到O(n × V)。这个"用容量换时间"的取舍，是整个算法成立的根基。

2. 二维dp是怎么一步步推出来的

2.1 阶段、状态、决策三件套

动态规划的三要素在背包问题上对应得特别干净：

• 阶段：处理到第几件物品了，用i表示，从 0 到 n。
• 状态：dp[i][j]表示"只考虑前 i 件物品、背包容量恰好为 j（不要求装满，指的是容量上限为 j）时能取得的最大价值"。
• 决策：第 i 件物品，取还是不取。

状态定义里最容易出错的是"恰好为 j"和"不超过 j"的区别。我建议初学者统一按"容量上限为 j"来理解，dp[i][j]的含义就是"前 i 件物品在容量不超过 j 的情况下能拿到的最大价值"。这样初始化全 0 就天然成立：一件都不拿，任何容量下的最大价值都是 0。

无后效性也就体现在这里：一旦我决定好了前 i 件物品怎么处理，后面第 i+1 件物品怎么选，只跟"还剩多少容量"有关，跟前 i 件具体选了哪几件无关。这个性质是压缩空间的前提，记住它，后面一维数组的推导全靠它。

2.2 状态转移方程与边界

对第 i 件物品（下标从 0 开始，第 i 件对应w[i]、v[i]）只有两种选择：

不取它，最大值就是从上一阶段继承：dp[i-1][j]。

取它，前提是j >= w[i]，那么最大值是dp[i-1][j - w[i]] + v[i]。这里的关键在于取的时候查的是dp[i-1][...]而不是dp[i][...]，因为每件物品只能用一次，取了第 i 件之后，剩余容量只能在"前 i-1 件"里做文章，绝不能再去考虑第 i 件。

于是：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) 当 j >= w[i] dp[i][j] = dp[i-1][j] 当 j < w[i]

边界条件是dp[0][j] = 0，也就是一件物品都不考虑时，任何容量的最大价值都是 0。还有一行隐藏的边界：j < w[i]时第二项不存在，直接继承上一行。这两条看起来简单，但它们决定了循环里if判断怎么写。

2.3 用一组小数据手工跑一遍二维表

空谈公式没用，我们拿一组数据把整张表算出来，后面一维的对比全靠这张表。

物品与价值：

背包容量V = 4。

第一行（只考虑物品0）：容量 0 拿不了，容量 1、2、3、4 都能拿物品0。

dp[0][j] = 0, 15, 15, 15, 15

第二行（加上物品1，重量3价值20）：

• j = 2时j < 3，继承dp[0][2] = 15
• j = 3时max(dp[0][3]=15, dp[0][0]+20=20) = 20
• j = 4时max(dp[0][4]=15, dp[0][1]+20=35) = 35

dp[1][j] = 0, 15, 15, 20, 35

第三行（加上物品2，重量4价值30）：

• j = 3时j < 4，继承dp[1][3] = 20
• j = 4时max(dp[1][4]=35, dp[1][0]+30=30) = 35

dp[2][j] = 0, 15, 15, 20, 35

最终答案是35，对应取物品0和物品1，重量 1+3=4，价值 15+20=35。注意物品2虽然单价最高，但塞进去之后就装不下别的了，反而亏。

这张表后面会被反复引用：一维数组正确跑完一遍的结果，必须逐格等于这张二维表的最后一行。这是判断一维写法对不对的唯一硬标准，也是对拍测试的对照物。作者自己写代码的时候，如果一时想不通某段循环为什么那样写，就把这张表拿出来比一比，比空想快得多。

3. 从二维压到一维：滚动数组到底省了什么

3.1 二维转一维的观察点

盯着上面那张表看三十秒，你会发现一个很重要的规律：算dp[i][j]的时候，用到的只有dp[i-1][j]和dp[i-1][j-w[i]]，全部来自上一行。前一行的数据在算完当前行之后就没用了，再往上第 i-2 行更是彻底作废。

既然只用上一行，那开 n+1 行就是纯浪费。一个自然的想法是：能不能只留一行，在这一行上"就地更新"，把上一行的值覆盖掉？

可以，但有个前提：覆盖的时机必须保证你还没用到这个位置上的旧值。这就是后面所有讨论的核心矛盾。

3.2 一维数组每一轮代表什么

压成一维之后，dp[j]的含义需要重新说清楚，否则一定会绕晕。准确的说法是：

在第 i 轮循环（也就是处理完前 i 件物品）结束之后，dp[j]表示前 i 件物品在容量上限 j 下能取得的最大价值。而在第 i 轮循环进行过程中，dp[j]里装的是"上一层（前 i-1 件物品）"的答案，只有被本轮访问过的位置才会被刷新成"当前层"的答案。

这个"进行中混合了新值和旧值"的状态，是理解倒序遍历的关键。因为一维数组没有行列之分，同一块内存里同时躺着两层的信息，哪个位置是新值、哪个位置是旧值，完全由遍历顺序决定。

写成伪代码就是：

for i in 0..n-1: for j in 从某个方向遍历 0..V: if j >= w[i]: dp[j] = max(dp[j], dp[j - w[i]] + v[i])

内层那个"从某个方向"，现在必须给出答案。而答案不是想当然的，得从"dp[j-w[i]]到底代表哪一层"这个角度去推。

3.3 内层循环的下界不能随意放

顺手提一个容易被忽略的细节：内层循环其实没必要从V一路跑到w[i]以下再判断。写成

for j in range(V, w[i] - 1, -1):

直接让下界停在w[i]，天然就避开了j < w[i]的情况，少一层判断，代码也更短。这不算什么大优化，但在面试手写代码时能少写一行if，观感更利落。真正需要注意的是 Python 的range是左闭右开，终止值必须写w[i] - 1而不是w[i]，这个 off-by-one 我第一次写的时候也栽过，结果少更新了一个位置，答案生生差了一档。

4. 倒序遍历背包容量的真正原因

4.1 先看正序会发生什么

假设我们把内层改成正序，也就是j从w[i]递增到V，还是用物品0（重量 1，价值 15）来演示，初始dp = [0,0,0,0,0]。

j = 1: dp[1] = max(dp[1], dp[0] + 15) = max(0, 0 + 15) = 15 j = 2: dp[2] = max(dp[2], dp[1] + 15) = max(0, 15 + 15) = 30 j = 3: dp[3] = max(dp[3], dp[2] + 15) = max(0, 30 + 15) = 45 j = 4: dp[4] = max(dp[4], dp[3] + 15) = max(0, 45 + 15) = 60

结果dp[4] = 60。可整道题只有一件物品，它最多只能被拿一次，容量 4 的正确答案应该是 15。60 意味着什么？意味着物品0被装了四次。也就是说，正序循环把 0-1 背包悄悄变成了完全背包。

这就是那个"改成正序，结果还更大，看着更优"现象的来源。它不是更优，它是错的，它违反的正是"每件物品最多取一次"这条最根本的约束。

4.2 从"读到的是哪个值"看倒序

现在把j从V递减回w[i]，同样的物品0，初始dp = [0,0,0,0,0]：

j = 4: dp[4] = max(dp[4], dp[3] + 15) = max(0, 0 + 15) = 15 j = 3: dp[3] = max(dp[3], dp[2] + 15) = max(0, 0 + 15) = 15 j = 2: dp[2] = max(dp[2], dp[1] + 15) = max(0, 0 + 15) = 15 j = 1: dp[1] = max(dp[1], dp[0] + 15) = max(0, 0 + 15) = 15

结果dp = [0, 15, 15, 15, 15]，跟二维表的第一行一模一样，物品0只被用了一次。

差别出在哪？就出在dp[j - w[i]]这个被读取的位置上。

• 正序时，j - w[i] < j，而j - w[i]这个位置在本轮循环里已经被更新过了。也就是说，读到的dp[j-w[i]]是"本轮已经处理过的结果"，里面已经包含了当前物品 i。拿它去加v[i]，等于让物品 i 又被用了一次。一次加一次，循环走到底，物品 i 就被用了很多次。
• 倒序时，j - w[i] < j，而j - w[i]这个位置在本轮循环里还没轮到，它仍然是上一轮（前 i-1 件物品）留下的旧值。这正好就是状态转移方程里要的dp[i-1][j-w[i]]，语义完全吻合。

所以那句流传很广的总结其实很精确：倒序遍历，保证dp[j-w[i]]读到的是上一层的旧值，从而保证每件物品只用一次。

4.3 一张表看清"旧值"与"新值"

我做了张对照表，这是我认为理解倒序最直观的方式。假设数组内存是物理线性排列的，j从 0 到 4，本轮要处理物品1（重量 3，价值 20），上一轮结束后的dp是[0, 15, 15, 15, 15]。

先看倒序的做法：

再看正序的做法（把它当成完全背包）：

看到这里你可能会疑惑：这个例子里正序和倒序读到的都是旧值啊？对，因为物品1的重量是 3，j - w[i]跳得比较远，恰好跳出了本轮会连续更新的区域。这就说明一件事：正序的危害不是每次都暴露，它只在"j - w[i]恰好落在本轮已经更新过的区间里"时才显形。物品1之所以没出事，是因为dp[1]在本轮没被更新（j=1 < w=3，根本不进循环）。

换个物品就露馅了。物品0的重量是 1，j - 1永远紧跟在前一个位置，正序必然踩雷，所以我们才在 4.1 节看到dp[4] = 60这种离谱结果。

这就是为什么很多人"试了一下正序好像也对"——他们试的那组数据恰好有重量较大的物品，或者 V 比较小，误打误撞没触发。这种"看起来对"是最危险的，因为它会让人带着错误认知去写下一题。

4.4 别把倒序理解成"防止越界"

有一个流传很广的错误解释：说倒序是为了防止j - w[i]出现负数、防止数组越界。这个说法完全站不住脚。防越界靠的是循环下界j >= w[i]，跟正序倒序一点关系都没有——正序从w[i]开始跑，同样不会越界。

倒序的唯一目的，就是保护dp[j-w[i]]这个被依赖位置的旧值不被提前覆盖。这是"就地更新时，被依赖的位置必须晚于依赖它的位置被更新"这条通用规则在背包问题上的具体体现。同一条规则在很多滚动数组的题里都出现过，比如最长公共子序列压缩成一维的时候，之所以需要额外用一个临时变量保存dp[j-1]的旧值，也是同一个道理——只是背包问题里j - w[i] < j这个关系恰好和"倒序遍历"天然契合，所以不需要临时变量。

提示：如果你在别的DP题里看到"一维数组需要从后往前更新"，多半也是同一个原因——避免覆盖掉本次计算还需要的上一层数据。判断方法是看转移方程里依赖的是同层的下标还是上一层的下标。

5. 为什么只能先遍历物品，不能先遍历背包

5.1 阶段和状态的位置不能换

前面说过，0-1背包的阶段是"物品编号 i"，状态是"容量 j"。阶段必须放在最外层，这不是什么编码习惯，而是动态规划递推的结构性要求。

原因在于，每一轮阶段推进，我们都在做一次"信息封存"：处理完第 i 件物品之后，dp数组里装的应该是"前 i 件物品在所有容量下的最优解"，第 i 件物品的选/不选这件事就永久定下来了，后面不会再翻案。这个"整行一次性刷新"的过程，只能由外层循环承担。

如果把容量放外层，会发生什么？外层每推进一格容量 j，内层就把所有物品扫一遍。这时dp数组里装的既不是"前 i 件物品"的结果，也不是"前 i-1 件物品"的结果，它是一堆跨越了所有物品、只处理了部分容量的中间态。你根本没办法把dp[j]对应到任何一张二维表的某一行上，语义直接崩了。

5.2 用具体数据把"先遍历背包"的错摆出来

空说结构不够，我们直接把代码跑出来看结果。

两组数据：物品0 重量 1 价值 15，物品1 重量 2 价值 20，容量V = 3。正确答案是物品0 + 物品1，重量 3，价值 35。

先试"外层容量从小到大，内层物品"：

j = 1: 物品0: dp[1] = max(0, dp[0]+15) = 15 物品1: 放不下 j = 2: 物品0: dp[2] = max(0, dp[1]+15) = 30 物品1: dp[2] = max(30, dp[0]+20) = 30 j = 3: 物品0: dp[3] = max(0, dp[2]+15) = 45 物品1: dp[3] = max(45, dp[1]+20) = 45

结果是45，比正确答案 35 还大。丢人都丢在明面上：物品0 被用了三次（1+1+1=3，15×3=45）。外层容量递增，内层又每次都从头扫物品，两个方向的"重复使用"叠加在一起，物品被无限次塞进背包。

再试"外层容量从大到小，内层物品"：

j = 3: 物品0: dp[3] = max(0, dp[2]+15) = 15 物品1: dp[3] = max(15, dp[1]+20) = 20 j = 2: 物品0: dp[2] = max(0, dp[1]+15) = 15 物品1: dp[2] = max(15, dp[0]+20) = 20 j = 1: 物品0: dp[1] = max(0, dp[0]+15) = 15 物品1: 放不下

结果是dp[3] = 20。这个比正确答案小，因为算j = 3的时候，dp[2]和dp[1]还是初始的 0，两个物品根本组合不起来，容量 3 最后只塞进去了一件物品1。

两个方向，一个偏大一个偏小，没有一个是能用的。这就是"先遍历背包"为什么彻底不可行的实证。

换个角度再解释一次：倒序遍历之所以能救一维数组，前提是"外层固定了物品 i，内层在同一个物品的上下文中横向扫描容量，被依赖的位置总是本轮还没碰过的"。而一旦外层变成容量，这个前提就不存在了——你没法为"本轮"定义一个统一的物品上下文，dp[j-w]里混着哪些物品的贡献完全说不清楚。

5.3 什么情况下反过来写反而是对的

这里必须补一句，否则容易走进另一个极端，觉得"先遍历容量"永远是错的。在一些只问方案数、不问最优值的计数型题目里，内外层的顺序决定了你到底在数什么，两者都是正确答案，只是含义不同。

举个例子，用面额 1、2、5 凑出 5 元。如果问"有几种组合方式"，答案是 4 种（5；1+1+1+1+1；1+2+2；1+1+1+2），要外层物品、内层容量。如果问"有几种排列方式"，那就是 9 种，因为 1+2+2、2+1+2、2+2+1 要算三种，得外层容量、内层物品。

判断依据很朴素：外层循环决定"谁是阶段、谁是状态"。当阶段在外层时，每件物品只会被作为一次独立的决策批次处理，天然不区分顺序；当容量在外层时，容量是阶段，每次推进都可以重新挑选任意一件物品，顺序信息被保留了下来。

所以"不能先遍历背包"这句话有严格适用范围：它针对的是求最优值的一维压缩写法。计数场景下反过来写是另一种题，不是错，是换了问法。

6. 一维写法的完整实现与边界细节

6.1 三种语言的实现

Python 版本，最常见也最简洁：

def knapsack_01(weights, values, cap): # dp[j] 表示容量上限为 j 时能取到的最大价值 dp = [0] * (cap + 1) for i in range(len(weights)): w, v = weights[i], values[i] # 倒序遍历：保证 dp[j - w] 读到的是上一件物品的旧值 for j in range(cap, w - 1, -1): dp[j] = max(dp[j], dp[j - w] + v) return dp[cap]

C++ 版本：

int knapsack01(const std::vector<int>& w, const std::vector<int>& v, int cap) { std::vector<int> dp(cap + 1, 0); for (size_t i = 0; i < w.size(); ++i) { for (int j = cap; j >= w[i]; --j) { dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]); } } return dp[cap]; }

Java 版本：

int knapsack01(int[] w, int[] v, int cap) { int[] dp = new int[cap + 1]; for (int i = 0; i < w.length; i++) { for (int j = cap; j >= w[i]; j--) { dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]); } } return dp[cap]; }

三段代码的结构完全一致，把倒序那行改成正序，三者就会同步错。所以任何一道题，我在写完一维版本之后都会立刻拿一组小数据手动对一遍，或者直接跟二维版本对拍，不给自己留"看着像对"的余地。

6.2 初始化改一个字，语义就换了一道题

dp数组的初始值直接决定题目问的是什么：

• 不要求装满：dp = [0] * (cap + 1)，所有容量都天然可达（大不了什么都不装，价值 0）。
• 恰好装满：dp = [NEG] * (cap + 1); dp[0] = 0，其中NEG是负无穷。除容量 0 之外的位置都需要靠状态转移"凑"出来，凑不出来的就是负无穷，最后如果dp[cap]还是负数，说明装不满，要按题目要求返回特定值。

代码长这样：

NEG = float('-inf') dp = [NEG] * (cap + 1) dp[0] = 0 for i in range(len(weights)): w, v = weights[i], values[i] for j in range(cap, w - 1, -1): if dp[j - w] != NEG: dp[j] = max(dp[j], dp[j - w] + v)

那个if dp[j - w] != NEG判断不是可选项。如果不加，负无穷加上一个正价值有可能变成一个"看起来合法"的数值（在浮点数下-inf + x仍然是-inf，但如果你用-1之类的整数代替负无穷，就会出问题），进而污染整个答案。所以我更倾向于用足够小的整数，比如-10**9，并且在转移时显式判断可达性。

6.3 求方案数和求最优值的写法差异

顺手把方案数的版本也写出来，因为倒序遍历在这类题里同样是刚需：

def count_ways_01(weights, cap): dp = [0] * (cap + 1) dp[0] = 1 for w in weights: for j in range(cap, w - 1, -1): dp[j] += dp[j - w] return dp[cap]

这里dp[j] += dp[j-w]读的必须是"还没把当前物品算进去"的方案数，否则同一个物品会被重复计入。倒序的理由和求最优值时完全一致。

6.4 两个不影响正确性但影响效率的剪枝

第一个是内层循环的上界可以收紧。处理第 i 件物品时，容量没必要从cap一路扫下来，因为前面 i 件物品的总重量是有限的，超过这个总和的位置不可能有变化。设sumW为前 i+1 件物品的总重量，循环上界写成min(cap, sumW)就行。在物品多、容量大的测试用例上，这个剪枝能省下可观的时间。

第二个是下界的收紧，理论上可以算max(w[i], cap - 后面所有物品的重量之和)，因为如果连后面所有物品都填不满剩余空间，这个位置本轮就不可能有改进。这个优化通常只在物品总重量远小于容量时才有意义，一般场景不用折腾。

7. 常见问题与排查速查表

7.1 出错现象与根因对照

这些年被问到的问题里，一维背包的错误翻来覆去就那么几类，我整理成一张表，你在调试时可以直接对号入座：

这张表里我觉得最值得反复看的是第一行和第二行。它们是一个硬币的两面：倒序遍历解决的是"层内覆盖"问题，物品在外层解决的是"阶段划分"问题。两个问题独立存在，缺一个都不行。我见过有人把倒序改对了，但因为物品和容量顺序写反，结果还是错的，然后以为是倒序没起作用，又改回正序，越调越乱。

7.2 用对拍法验证自己的一维写法

最高效的自检方法不是盯着代码看，而是写两个函数：一个二维版本（逻辑直观、几乎不会写错），一个一维版本（效率高但容易出坑），然后造小规模随机数据对拍。

import random def brute(weights, values, cap): """暴力搜索，作为最终对照""" n = len(weights) best = 0 for mask in range(1 << n): tw = tv = 0 for i in range(n): if mask >> i & 1: tw += weights[i] tv += values[i] if tw <= cap: best = max(best, tv) return best for _ in range(2000): n = random.randint(1, 8) cap = random.randint(1, 15) weights = [random.randint(1, 8) for _ in range(n)] values = [random.randint(1, 20) for _ in range(n)] a = knapsack_01(weights, values, cap) b = brute(weights, values, cap) assert a == b, (weights, values, cap, a, b)

跑上两千组，如果全部通过，基本可以确认一维写法没问题。这个对拍的习惯我从写第一道背包题开始就养成了，直到现在还在用，因为它能在几十毫秒内把"我觉得应该对"变成"数据说它确实对"。尤其是当你在纠结内外层顺序、正序倒序这些细节的时候，与其在脑子里模拟循环，不如让机器替你试。

7.3 我自己踩过的三个坑

第一个坑是把dp数组的下标语义搞混。dp[j]里的j是容量上限，不是"装了多少件"。有一次我在方案数版本里把dp[j]当成"容量恰好为 j"，但初始化又写了全 0，结果容量 1 到 4 全都返回了 1 种方案，因为"什么都不装"被当成了合法方案。后来我养成一个习惯：写初始化之前，先用一句话把dp[j]的中文含义念出来，念不通就是自己没想清楚。

第二个坑是在剪枝的时候把上界写成了cap，下界又写了w[i]，但物品数组没按重量排序，导致j - w[i]在某些轮次里访问到了一个"尚未进入有效状态"的位置。那题的结论是，剪枝一定要在保证语义不变的前提下做，任何"我觉得这样更快"的改动，都要回到对拍脚本里验证。

第三个坑是语言层面的。Python 的range(cap, w - 1, -1)如果写成range(cap, w, -1)，会少遍历一次j = w，而这个位置往往恰好是"只放当前物品"的最优解。这个错误在复杂用例上不一定暴露，但在cap恰好等于某件物品重量时必错。所以我在写循环边界时，尤其是递减的range，都会多念一遍"右开区间"。

8. 把这套思路迁移到同类问题上

背包问题的这套分析方法，其实可以整套搬到别的题上去，这是我觉得它最值钱的地方。

判断一道题能不能用"一维倒序压缩"，我会问自己三个问题：

1. 每件物品（每个决策单元）是不是至多被使用一次？如果是，内层必须倒序；如果可以用无限次，内层就得正序，这是完全背包；如果可以用有限次，那就得拆成二进制组或者用单调队列优化。
2. 依赖关系指向的是"上一层"还是"同一层"？指向上一层，就是倒序保护旧值；指向同一层，就是正序利用新值。转移方程里下标是谁，答案基本就定了。
3. 阶段是哪个维度？阶段必须在最外层。物品、天数、区间长度、字符串下标，哪个维度承载了"不可回退的推进"，哪个就该放到最外面。

拿最长回文子序列、编辑距离这类题套一下也完全对得上：它们的阶段是区间长度，容量维度被换成了字符串位置，一维压缩时同样要考虑覆盖顺序。我甚至写过一个用来检查"一维压缩是否合法"的小脚本，把转移方程里的下标关系解析出来，自动提示哪些位置需要倒序——虽然最后没做成什么正经工具，但写那个脚本的过程让我彻底记住了这条规则：被依赖的位置，必须在依赖它的位置之后被更新。

回到这道题本身，最后再补一句实操层面的建议。如果你正在准备面试或者刷题，遇到一维背包卡壳的时候，不要在网上反复搜"为什么倒序"的解释，直接打开编辑器，把那几行循环改成正序跑一遍，把dp数组每一轮的值打印出来，和二维版本逐行比。看到dp[4]从 15 变成 60 的那一瞬间，你就不需要任何人再给你解释了——那个 60 会替你记住一切。我自己就是这么记下来的，比看十篇文章都管用。