0-1背包这道题几乎是所有人学动态规划时绕不过去的第一道坎。二维写法大家都觉得顺理成章可一旦把数组压成一维问题就来了为什么背包容量那一层循环必须倒着走为什么两层循环的顺序不能颠倒只能先遍历物品、再遍历背包我在带新人刷题的时候发现很多人能把代码背下来但被追问一句凭什么是这样就卡壳了。这篇就把这两个问题从头到尾拆开讲一遍重点是解释清楚一维dp数组的倒序遍历背后的状态依赖逻辑以及遍历顺序为什么被锁死。如果你正在学背包、或者曾经能写但说不清这篇应该能帮你把这块拼图补上。1. 先把0-1背包到底在决策什么理清楚很多教程一上来就给方程结果读者只知道套公式不知道公式在算啥。我们先把问题本身讲透后面解释遍历顺序时你才能跟得上。1.1 每个物品只能选或不选一次0-1背包的设定是这样的有n件物品第i件物品的重量是w[i]、价值是v[i]。现在有一个容量为V的背包要求从这些物品里挑一部分装进去让总重量不超过V的前提下总价值最大。关键在那个0-1上——每件物品要么整个拿走要么完全不要不允许拿一半也不允许同一件拿两次。这就是它和分数背包可以拿一部分和完全背包每件可以无限拿的根本区别。这个约束看起来简单却是后面所有遍历顺序推导的起点。你把它想象成搬仓库每件货是整箱的箱子不能拆车只有一辆装不下就下次再来。你现在的目标不是装得最多而是装得最值。这就是一个典型的有限资源下的组合优化问题。朴素做法是枚举所有子集2^n种组合n稍微大一点就炸了。动态规划的价值就在于把这种指数级的枚举压成了多项式级别的递推。1.2 二维dp的状态定义与转移方程二维写法是最贴近直觉的。我们定义dp[i][j]表示只考虑前i件物品、背包容量为j时能获得的最大价值。为什么这么定义状态因为决策是一步一步做的——每增加一件物品我们都面临一个二选一这件物品放还是不放。不放那价值就等于前i-1件、容量j的最优值即dp[i-1][j]。放前提是j w[i]。放进去之后容量还剩j - w[i]价值在前i-1件、容量j-w[i]的基础上加上v[i]即dp[i-1][j-w[i]] v[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])注意这里最要紧的一点**右边的状态全部来自第i-1行。**也就是说dp[i][j]只依赖它上一行的数据跟本行i的其他格子没有关系。这个依赖关系是理解后面一切遍历顺序的地基务必记住。1.3 从二维压到一维滚动数组的取巧二维写法很清楚但它开了一个n × V的表。当n和V都不小的时候内存开销是实打实的。有没有办法省掉一维答案是有的因为我们发现了一个事实**算第i行时只用到第i-1行更早的行根本不用了。**每算完一行上一行就可以被覆盖。既然如此为什么还要老老实实保存所有行呢只留一行跟着物品一件件滚动更新就好了。于是我们定义一维的dp[j]表示当前处理到的物品范围内、容量为j时能获得的最大价值。转移方程变成dp[j] max(dp[j], dp[j-w[i]] v[i])这里的dp[j]等号右边的那个其实就是二维里的dp[i-1][j]而dp[j-w[i]]对应dp[i-1][j-w[i]]。但请注意——这个对应关系成立是有前提的前提就是dp[j-w[i]]在你读取它的那一刻必须还是上一轮也就是还没处理当前物品i的值。一旦它被本轮更新过了对应关系就崩了计算也就错了。这就是为什么遍历方向这么要命。下面我们用具体例子把这件事彻底跑一遍。2. 一维dp数组正序遍历为什么会让物品复活这一节是全文的核心慢慢看。很多人对倒序的理解停留在背下来就行但只要能看懂一个反例就永远不会记错了。2.1 一个反例就能看出正序的问题假设只有一件物品重量w 1价值v 15。背包容量V 3。按 0-1 的规矩这件物品最多只能拿一次所以无论容量多大最优价值都应该是15。现在假设我们一维数组用正序遍历也就是j从w一直加到V// 错误示范正序 for (int i 0; i n; i) { for (int j w[i]; j V; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }手动跟一遍j 1dp[1] max(dp[1], dp[0] 15) max(0, 0 15) 15。j 2dp[2] max(dp[2], dp[1] 15)。此时dp[1]刚刚被更新成了15所以dp[2] max(0, 15 15) 30。j 3dp[3] max(dp[3], dp[2] 15)。dp[2]也是本轮刚更新的30于是dp[3] 45。出大问题了。说好的一件物品只能拿一次结果dp[3]等于 45等于这件物品被塞了三次。为什么因为正序遍历时当你处理较大的容量jj - w[i]是一个比j小、已经被本轮更新过的容量里面已经包含了当前这件物品。你再往上加一件就相当于在同一轮里把同一件物品算了又算。这就是 0-1 背包里最经典的错误——正序会把它变成完全背包也就是每件物品可以拿无限次的那种问题。2.2 dp[j-w[i]] 到底代表哪一轮的状态把上面那件事上升到理论层面。二维里dp[i][j]依赖的是dp[i-1][j-w[i]]注意下标是i-1是上一行。在压缩成一维后我们用同一个数组反复覆盖。那么如果dp[j-w[i]]保持的是处理物品i之前的值那它刚好对应dp[i-1][j-w[i]]正确。如果dp[j-w[i]]已经被处理物品i时更新过了那它对应的是dp[i][j-w[i]]也就是同一行的值这就违反了原始依赖语义错乱。正序遍历j的时候j-w[i] j也就是说较小的容量总是先被处理。等你走到容量j时j-w[i]早就更新完了读到的是本轮的新值——于是你拿到的是dp[i][j-w[i]]对应关系错了物品被重复使用。倒序遍历j的时候j从大到小走j-w[i] j较小的容量还没轮到。等你处理容量j时j-w[i]还停留在上一轮的旧值——也就是dp[i-1][j-w[i]]完美对应正确。所以倒序的本质是用遍历方向控制你读到的子状态是新的还是旧的。这一点跟你在操作线性表、数组时确认下标从哪头开始扫是一个道理——同一个数据结构遍历方向不同读到的内容可能是两码事。2.3 倒序遍历如何锁住上一轮把上面的话收成一句口诀容量倒着走读到的dp[j-w[i]]就是上一件物品处理完之后的值容量正着走读到的就是当前物品已经处理过的值。我们把dp[j]在更新过程中的角色说得再直白点遍历方向读取 dp[j-w[i]] 时它代表的状态物品是否会被重复使用正序j 从 w 到 Vdp[i][j-w[i]]本行新值会退化成完全背包倒序j 从 V 到 wdp[i-1][j-w[i]]上一行旧值不会符合 0-1 语义还有个小细节值得提容量为什么从V走到w[i]就停而不是走到 0因为当j w[i]时j - w[i]是负数这件物品根本放不下dp[j]保持原值即可没必要处理。这属于边界剪枝对答案没影响但能少跑一部分循环。到这里第一个问题——为什么倒序——应该清楚了。但仅仅倒序还不够另一个隐藏的坑是为什么两层循环只能先物品、后背包颠倒过来为什么也错我们接着往下拆。3. 为什么必须先物品后背包颠倒顺序就崩很多人的理解只停在倒序上却忽略了外层循环的顺序同样是被锁死的。下面我们把四种组合排列出来一个个看。3.1 遍历顺序的四种组合逐一排雷两层循环一层是物品i一层是容量j每层各自还能正序或倒序组合起来就是四种。我们逐个判断先物品、容量倒序正确这是标准 0-1 写法。先物品、容量正序错退化成完全背包第 2 节已证明。先容量、物品内层错无论容量正序倒序都会出问题。先容量、物品外层同上错。也就是说只有先物品、容量倒序这一种是对的。前三种为什么错前两种我们已经讲了重点看后两种——先容量、后物品这才是最容易被忽视的坑。先给个直觉一维数组是按物品为单位滚动更新的每处理完一个物品整行dp就整体往前推进一轮。所以外层必须是物品一层一层滚。如果你把容量放到外层就等于按容量来推进而容量之间并没有物品那种行的关系滚动的前提就被破坏了。3.2 用一个具体例子跑出错误答案光说直觉不够我们上代码跑一遍。物品两件Aw2, v3Bw3, v4。容量V 5。正确的答案是 A B总重235总价值7。先用标准写法先物品、倒序容量验证for (int i 0; i 2; i) for (int j V; j w[i]; j--) dp[j] max(dp[j], dp[j - w[i]] v[i]);跟一遍处理 Adp[5]3, dp[4]3, dp[3]3, dp[2]3。处理 Bj5: dp[5]max(3, dp[2]47)7j4: dp[4]max(3, dp[1]44)4j3: dp[3]max(3, dp[0]44)4。结果dp[5]7正确。现在换成先容量、后物品容量仍然倒序for (int j V; j 0; j--) for (int i 0; i 2; i) if (j w[i]) dp[j] max(dp[j], dp[j - w[i]] v[i]);跟一遍初始全 0j5先看 Adp[5]max(0, dp[3]3)。此时dp[3]还是 0尚未处理到j3得3再看 Bdp[5]max(3, dp[2]44)4。j4A 给出dp[4]max(0, dp[2]33)3B 给出dp[4]max(3, dp[1]44)4。j3A 给出dp[3]max(0, dp[1]33)3B 给出dp[3]max(3, dp[0]44)4。j2A 给出dp[2]3B 放不下。最终dp[5]4是错的。为什么因为在处理容量 5 的时候它依赖的dp[3]和dp[2]还都是旧值0 或原始值根本没有把 A 装进去。等后面处理到dp[3]、dp[2]并把 A 更新进去时dp[5]早就算完了再更新也轮不到它。根子在于容量之间没有逐行推进的关系你把容量放外层就等于每个容量只在自己那一轮里被草草决定一次完全无法累积多个物品。3.3 从二维依赖关系看行优先的本质回到二维方程再看一眼dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])这是一张表i是行、j是列。注意dp[i][j]依赖的是同一列上一行dp[i-1][j]和左边一列上一行dp[i-1][j-w[i]]——两个都在第i-1行。换句话说算第i行之前第i-1行必须整行算完一行一行往下走。这就是所谓的行优先填表顺序。压缩成一维后行就变成了物品整行算完变成了整件物品的所有容量都更新完所以外层必然是物品内层才是容量。如果你先遍历容量就相当于按列优先填表而列与列之间并不存在能支撑递推的完整前序状态——算某一列时它的左邻列还没算好依赖就断了。一句话总结这一节先物品保证每一轮是一个完整的状态层倒序容量保证读取到的是上一层。前者管行后者管列缺一不可。4. 手把手推演完整代码与逐格验证理论讲完落地一遍。把标准代码写出来再用打印技巧亲眼看见dp是怎么一轮一轮滚动的。4.1 标准一维写法与边界处理#include vector #include algorithm using namespace std; int knapsack01(vectorint w, vectorint v, int V) { vectorint dp(V 1, 0); int n w.size(); for (int i 0; i n; i) { // 外层物品 for (int j V; j w[i]; j--) { // 内层容量倒序 dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[V]; }几个容易忽略的点dp大小是V 1因为要表示从 0 到 V 的所有容量别开成V。初始化为全 0表示一件不放时价值为 0这是求最大价值不超过容量的标准初始化。内层循环下界是w[i]不是 0负数容量的情况下直接跳过。外层从第 0 件开始注意下标别写成从 1 开始去访问w[1]而漏了w[0]。对应地Python 版本更短def knapsack01(w, v, V): dp [0] * (V 1) for i in range(len(w)): for j in range(V, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[V]Python 里range(V, w[i]-1, -1)就是从 V 递减到 w[i]把倒序表达得很清楚。注意终止值写w[i]-1而不是w[i]因为range是取不到的右开边界。4.2 打印dp数组观察中间状态光看代码不放心建议你在调试时把每轮之后的dp打出来。还是用 Aw2,v3、Bw3,v4、容量 5 的例子for (int i 0; i n; i) { for (int j V; j w[i]; j--) dp[j] max(dp[j], dp[j - w[i]] v[i]); // 打印本轮结束后的 dp printf(处理物品 %d 后: , i); for (int j 0; j V; j) printf(%d , dp[j]); printf(\n); }你会看到类似这样的输出轮次dp[0]dp[1]dp[2]dp[3]dp[4]dp[5]初始000000处理A后003333处理B后003447亲眼看见dp从初始全 0到装完 A、再到装完 B 的整行推进过程比空想有用得多。尤其注意处理 B 时dp[5]是怎么拿到dp[2] 3的——那个 3 是上一轮A 处理完的值是 A 贡献的所以dp[5]才顺利变成 7。这正是倒序保住的上一轮。4.3 常见错误写法与对照把坑集中列一下方便你自查错误写法表现本质原因内层容量正序结果偏大物品被重复使用读到了本轮新值退化成完全背包先循环容量后循环物品结果偏小物品无法组合容量间无递推状态层不完整初始化全为 0 但要求恰好装满结果偏大空背包被当成合法方案内层下界写成 0可能数组越界或计算错误忽略了j w[i]放不下这四条里前两条是本篇的重点后两条属于边界和初始化的细节坑第 5 节还会展开讲。5. 把几个容易混淆的变体放一起对照只看 0-1 背包容易把结论记死把相近的变体摆在一起你会更明白遍历顺序到底在控制什么。5.1 完全背包为什么反而要正序完全背包的规矩是每件物品可以拿无限次。它的转移里dp[j]依赖的恰好是本行的dp[j-w[i]]因为可以继续拿同一件而不是上一行。既然依赖的是本行新值那正序遍历就刚好合适——你就是希望读到被当前物品更新过的值这样同一件物品才能被叠加进去。对照记就很简单0-1 背包每件最多一次读上一行所以容量倒序。完全背包每件无限次读本行所以容量正序。方向反过来问题性质就变了。这也是为什么第 2 节的反例里正序会让 0-1 背包长出完全背包的行为。5.2 组合数与排列数的遍历顺序差异再深一层还有一类容易被遍历顺序影响的问题求装满背包的方案数。这时候区分组合数和排列数靠的就是两层循环的顺序。如果外层物品、内层容量物品的自然顺序被固定先放谁后放谁不会产生新方案算出来的是组合数不看顺序。如果外层容量、内层物品同一组物品会因为放入顺序不同被重复计数算出来的是排列数看顺序。这说明两层循环的顺序不只是对不对的问题还会直接改变你统计的语义。回到 0-1 背包我们要的是每种选取组合只算一次价值最大所以自然用先物品、后容量并且容量倒序。5.3 初始化与恰好装满的坑初始化常被忽略但它会悄悄改变答案的含义。还是那句话dp的初值代表了多么空的状态算合法。求容量不超过 V 的最大价值dp全部初始化为 0。理由是空背包价值为 0且任何没装满也是允许的。求恰好装满容量 V 的最大价值dp[0] 0其余全初始化为负无穷或用-1标记不可达。因为只有容量 0 才是天然的恰好装满且价值 0其他容量在没放任何物品时是不合法的要用负无穷排除掉。我见过不少人求恰好装满时忘了改初始化结果答案虚高——本质就是把空着没满当成了合法方案。这跟遍历顺序无关但和背包问题是绝配的一对坑一起记住更省事。6. 我在实际刷题中沉淀下来的几条经验讲到这里核心的两个问题——倒序、顺序——应该都清楚了。最后补几条我自己踩过、觉得最值的经验帮你在实战里少走弯路。第一条别背口诀背依赖关系。很多人把0-1倒序、完全正序当顺口溜背结果一遇到变形题就懵。真正要记的是dp[j]依赖的是哪一轮的dp[j-w[i]]。判断的方法很简单——问自己这件物品能不能被重复使用。不能就要读旧值那就倒序能就要读新值那就正序。依赖关系一清楚方向自己就出来了。第二条调试时一定要打印中间数组。像第 4.2 节那样每轮结束打印一次dp看着它一行行滚动。这个方法我在讲背包、讲一维化的时候反复用效果特别好因为它把抽象的状态依赖变成了能看见的数值变化一眼就能发现哪个dp[j]拿错了值。第三条验证顺序问题时构造极端小例子。就一件物品容量给 3一跑就知道正序会重复。用最小例子验证遍历顺序比用什么大测试都直接。第四条写代码时先写二维确认逻辑对了再压一维。二维写法不容易错压一维只是省空间逻辑应该完全一致。如果你直接上一维一旦遍历顺序写错报出来的错又很隐蔽排查成本高得多。先二维、后一维是稳妥路线。第五条把先容量后物品这件事当成红线。我见过太多人是被这个小坑绊倒的——倒序写对了但循环顺序反了结果怎么都对不上。记住一维数组是按物品为单位滚动的物品这层必须在外这是结构决定的不是随便排的。把这几条吃透0-1 背包的一维写法基本就不会再错了。至于那个顺序表的建立及遍历的热词其实讲的也是同一件事的另一面——数据结构的遍历方向决定了你读到的是新值还是旧值放到一维 dp 数组上这个方向就变成了决定 0-1 还是完全背包的分水岭。想通这层联系以后遇到别的滚动数组优化你也能一眼看穿它该往哪头扫。