背包类问题在动态规划里属于绕不开的经典题型而完全背包问题又是其中最容易“以为自己懂了、一写就错”的那一类。很多人第一次接触它时脑子里装的是 01 背包的模板结果把内层循环改成倒着写、正着写都试了一遍提交上去一半通过一半超时最后连初始化该填 0 还是填负无穷都开始怀疑人生。我自己当年也是踩过这个坑的明明状态转移方程只差一个下标跑出来的答案却能差出十万八千里。这篇文章就是想把完全背包问题从朴素解法到空间优化的完整推导过程掰开揉碎讲清楚尤其是“为什么一维数组的内层循环要正着走”这个卡了无数新手的点。适合正在刷动态规划入门题、被多重循环绕晕或者想系统整理背包九讲的在校学生和算法爱好者。1. 问题定义与模型抽象1.1 完全背包到底在描述什么场景先把题目本身说清楚。完全背包问题的标准描述是这样的有 N 种物品每种物品都有一个体积也叫重量、代价w[i] 和一个价值 v[i]并且每种物品可以取无限多次。现在给一个容量为 W 的背包问在不超容量的前提下能装下的最大总价值是多少。这里的“无限多次”是关键定语。它区别于 01 背包的“每种最多取一次”也区别于多重背包的“每种最多取 s[i] 次”。换句话说完全背包的世界里只要你背包还有空间同一件东西你想塞几件就塞几件。我习惯用一个生活化的场景来记这个模型去自助餐厅拿菜盘子容量有限每样菜你都可以拿任意多份但每种菜每一份占的格子数和带来的满足感是固定的问怎么拿最划算。这个类比里“盘子容量”就是背包容量 W“菜的份数”就是物品个数“拿走无限份”对应完全背包的核心特征。相比之下01 背包就像限量供应的甜品每人只能拿一份多重背包就是“每人限拿三份”的那种规则。从数学上看完全背包就是这样一个整数规划问题在约束 Σ k_i · w_i ≤ W其中 k_i ≥ 0 为整数下最大化 Σ k_i · v_i。这里的 k_i 是每种物品取用的件数可以取 0也可以取很大。很多教材会把它写成 min 形式的“恰好装满求最小代价”但那是变体主体思路是一样的。1.2 为什么不能直接用贪心解决第一次看到这个问题的人往往会本能地想既然每样东西可以无限拿那我算一下每件物品的“性价比”单位体积的价值 v[i] / w[i]从高到低拿不就行了这个直觉在分数背包里是对的因为你可以把一件物品切开来拿但在完全背包里物品是整件的不能切。举个能直接打脸贪心的反例。背包容量 W 10有两件物品物品 A 体积 6、价值 8性价比 1.33物品 B 体积 5、价值 7性价比 1.4。按性价比排序会先拿 B剩 5 再拿一件 B总价值 14剩余 0。但最优解其实是拿一件 A 加一件 B体积 11 超了不行那拿两件 B 是 14而只拿一件 A 再加……拿不下了。换个例子容量 10物品 A 体积 6 价值 8物品 B 体积 4 价值 5物品 C 体积 3 价值 4。贪心按性价比先看 A1.33拿一件剩 4再拿一件 B总价值 13但最优是拿两件 B 加……448 剩 2 拿不了 C价值 10或者 BCC 433 10价值 54413还是 13。真正让贪心翻车的例子是“性价比高但体积也很大导致留着空间反而能装更多高性价比组合”的情况。经典反例W5物品一 w4, v5性价比 1.25物品二 w3, v4性价比 1.33物品三 w1, v1性价比 1。贪心先拿物品二1.33剩 2 拿两个物品三价值 426但最优是物品一加物品三415 体积价值 6换两个物品二体积 6 超了。这个例子其实贪心也没差所以我更愿意用这个W10物品 1: w7, v9物品 2: w5, v6物品 3: w3, v3。性价比物品11.29物品21.2物品31。贪心拿一件物品1剩3再拿一件物品3总价值 12。但最优是两件物品2体积 10价值 12或者一件物品1加……9剩3只能拿物品33合计12物品2物品212。也平了。老实说纯贪心在完全背包上失败的经典构造是W10物品 A w6 v7物品 B w5 v6物品 C w4 v5。性价比 A1.167, B1.2, C1.25。贪心按 C 先拿拿两件 C体积 8 价值 10剩 2 拿不了总价值 10但最优是 AC 体积 10 价值 12。看贪心输了。这说明局部性价比最优不等于全局最优必须用动态规划穷举所有组合。注意贪心只能在“物品可以任意分割”的分数背包里保证最优整件选取的场景一律要用动态规划。1.3 状态设计与维度选择动态规划的第一步永远是定义状态。完全背包最自然的状态设计是二维的dp[i][j]表示只考虑前 i 种物品当背包容量为 j 时能获得的最大价值。为什么是这两个维度因为决策过程是按“物品种类”一步步推进的每种物品我们要决定“拿几件”而约束是“背包容量”。二维状态恰好把“决策到哪一步”和“还剩多少资源”这两个信息都记录下来避免了后续决策依赖前面具体选择了什么。这就是动态规划里常说的“无后效性”——一旦确定了前 i 种物品在容量 j 下的最优结果后面的决策只跟这个结果有关不需要知道前面具体怎么拿的。对比一下 01 背包的状态设计其实一模一样区别只发生在转移时的下标细节上。这也是很多人迷惑的地方状态定义完全一样代码却差一个循环方向答案就完全不同。初始化要怎么填如果题目要求恰好装满那dp[0][j]容量 j 但没有任何物品可选里只有dp[0][0] 0是合法的其余dp[0][j]都要设成负无穷表示“不可能恰好装满”如果题目不要求装满大多数模板题都是这种那么dp[0][j]全部设成 0 即可因为空背包本身就是一种合法状态价值为 0。这个初始化差异是新手最容易忽视的细节我会在后面的排查章节专门讲。2. 从朴素解到一维优化的完整推导2.1 二维朴素解法的转移方程先写出最直白的二维转移方程。对于dp[i][j]我们面对第 i 种物品可以决定取 0 件、1 件、2 件……直到装不下为止。但不需要真的去枚举“取几件”因为动态规划可以用一个巧妙的转移把枚举过程省掉dp[i][j] max(dp[i-1][j], dp[i][j - w[i]] v[i])这个方程的含义要拆开看dp[i-1][j]表示第 i 种物品一件都不拿那么结果就等于只考虑前 i-1 种物品、容量 j 的最优值。dp[i][j - w[i]] v[i]表示至少拿一件第 i 种物品。注意这里用的是dp[i][j - w[i]]而不是dp[i-1][j - w[i]]——这正是完全背包的灵魂所在。因为取走一件第 i 种物品后剩下的容量里仍然可以继续取第 i 种物品所以还停留在“前 i 种物品”这个阶段而不是退回“前 i-1 种”。这个细节一对比就非常清楚。01 背包的方程是dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])因为每件物品只能拿一次拿完就必须退回上一层。完全背包把第二个下标里的i-1改成了i仅此一字之差就实现了“无限取”的能力。很多教程喜欢用“枚举 k 件”的写法即dp[i][j] max(dp[i-1][j - k·w[i]] k·v[i])k 从 0 枚举到 j/w[i]。这个写法正确但效率低枚举 k 会多一层循环。而上面那个dp[i][j-w[i]] v[i]的写法之所以等价是因为它把“再拿一件”的动作无限次地递归了下去本质上已经把枚举折叠进状态转移里了。2.2 空间优化为什么要压成一维二维数组dp[N][W]在 N 和 W 都不大时没问题但实战中 N 和 W 常常达到 10^3 甚至 10^4 量级二维数组会直接超内存。这时候就要做滚动数组优化。观察转移方程dp[i][j] max(dp[i-1][j], dp[i][j - w[i]] v[i])你会发现计算第 i 行时只依赖第 i-1 行的dp[i-1][j]和第 i 行左侧的dp[i][j-w[i]]。这说明我们没必要保留整个二维表用一个一维数组dp[j]就够了只要保证计算顺序能拿到正确的旧值和新值。关键问题来了这个一维数组的内层循环该正着走还是倒着走答案是完全背包必须正序从小到大遍历容量 j。原因是这样的当我们用一维数组dp[j]更新时dp[j] max(dp[j], dp[j - w[i]] v[i])右边的dp[j - w[i]]是容量更小的位置。如果 j 从小到大遍历那么在计算dp[j]时dp[j - w[i]]已经在本次 i 的循环中被更新过了它记录的是“已经考虑过第 i 种物品”的值——这恰好对应完全背包需要的dp[i][j-w[i]]。反过来如果倒序遍历dp[j-w[i]]还是上一轮 i-1 的旧值那就变成了 01 背包的语义。这就解释了那个困扰无数人的现象01 背包倒序完全背包正序一维代码里唯一的区别就是循环方向。我第一次搞懂这一点的时候瞬间觉得背包问题通透了不少。你可以自己拿个小例子手推一遍容量 5物品体积 2、价值 3正序遍历时dp[2]先被更新为 3然后dp[4]用到dp[2]3得到 6等价于拿了两件倒序遍历时dp[4]用到的是旧的dp[2]0得到 3只拿一件。手推一遍胜过看十遍公式。2.3 一维代码的正确模板把上面推导落地成代码。C 版本如下int completeKnapsack(int W, vectorint w, vectorint v) { int n w.size(); vectorint dp(W 1, 0); // 不要求装满全部初始化为 0 for (int i 0; i n; i) { for (int j w[i]; j W; j) { // 正序遍历这是与 01 背包的唯一区别 dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[W]; }Python 版本更直观def complete_knapsack(W, w, v): dp [0] * (W 1) for i in range(len(w)): for j in range(w[i], W 1): # 正序 dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[W]这段代码的时间复杂度是 O(N·W)空间复杂度 O(W)。对比二维版本的 O(N·W) 空间压缩得非常彻底。提示如果你把内层循环写成for (int j W; j w[i]; j--)就变成了 01 背包。一定要记住这个方向差异笔试面试被追问的时候大概率会考。3. 手推实例与优化细节拆解3.1 用一个小案例把过程跑一遍光看公式容易飘我们用一个具体例子走一遍。背包容量 W 8物品有三种物品体积 w价值 v123234345按照dp[j] max(dp[j], dp[j-w]v)的顺序逐个物品更新。初始化 dp 数组全 0下标 0 到 8。处理物品 1w2, v3j 从 2 遍历到 8j2: dp[2] max(0, dp[0]3) 3j3: dp[3] max(0, dp[1]3) 3j4: dp[4] max(0, dp[2]3) 6j5: dp[5] max(0, dp[3]3) 6j6: dp[6] max(0, dp[4]3) 9j7: dp[7] max(0, dp[5]3) 9j8: dp[8] max(0, dp[6]3) 12可以看到 dp[8]12等价于拿了四件物品 1正好填满价值 12。处理物品 2w3, v4j 从 3 到 8j3: dp[3] max(3, dp[0]4) 4j4: dp[4] max(6, dp[1]4) 6j5: dp[5] max(6, dp[2]4) 7dp[2]3拿一件物品2加一件物品1j6: dp[6] max(9, dp[3]4) 9dp[3]4448不如 9j7: dp[7] max(9, dp[4]4) 10dp[4]66410j8: dp[8] max(12, dp[5]4) 12处理物品 3w4, v5j 从 4 到 8j4: dp[4] max(6, dp[0]5) 6j5: dp[5] max(7, dp[1]5) 7j6: dp[6] max(9, dp[2]5) 9dp[2]3358不如 9j7: dp[7] max(10, dp[3]5) 10j8: dp[8] max(12, dp[4]5) 126511不如 12最终答案是 dp[8] 12。这个例子恰好说明贪心地只拿性价比最高的物品 1性价比 1.5确实拿到了最优但如果换一组数据贪心就会失效。手推的价值在于你能亲眼看到dp[j-w]用的是同行的新值这就是无限取的体现。3.2 恰好装满与不要求装满的初始化差异这是完全背包里最容易被忽略、又极其容易出错的点。两种题型在代码上的区别只在于初始化不要求装满求最大价值容量可以有剩余dp 数组全部初始化为 0。因为“什么都没装”是一种合法状态价值为 0而且余下的容量空着也允许。恰好装满容量必须用尽dp[0] 0dp[1..W] -∞或一个足够小的负数。为什么因为容量 0 恰好装满的合法状态价值是 0而容量大于 0 却没有任何物品时是“不可能装满”的非法状态用负无穷标记。这样在转移时如果dp[j-w[i]]是负无穷加上 v[i] 仍然是一个极大负数不会被误选为答案。我见过太多人在“恰好装满”的题上把 dp 全初始化成 0结果求出来的答案对应“没装满但价值虚高”的错误方案。记住这个口诀求最大值且不装满用 0恰好装满用负无穷如果求最小值则恰好装满用正无穷不装满也用 0但最小值问题少见。3.3 枚举“取几件”的写法为什么更慢前面提过朴素写法dp[i][j] max(dp[i-1][j-k·w[i]] k·v[i])k 从 0 到 j/w[i]。这个写法时间复杂度是 O(N·W·(W/w))最坏情况下近似 O(N·W²)在 W 较大时直接爆炸。而优化后的写法把枚举折叠掉降到 O(N·W)。这是完全背包优化过程里最核心的一次跃迁。为什么可以折叠因为“取 k 件”这个动作可以拆成“先取 1 件剩下容量再考虑还要不要取”而“剩下容量再考虑”这件事已经被dp[i][j-w[i]]这个状态描述过了。这就是动态规划最喜欢用的子问题重叠——把一个大决策拆成一连串相同结构的子决策每个子决策只做一次。心得很多背包变体比如带数量限制的多重背包之所以难就是因为不能直接这样折叠需要引入二进制拆分或单调队列优化。完全背包恰好是可以优雅折叠的那一类。4. 常见坑点与排查速查表4.1 内层循环方向写反导致答案偏小这是完全背包最高频的错误没有之一。症状是明明每件物品可以拿无数次跑出来的结果却总比正确答案小而且小得“像是每件只拿了一次”。原因就是把内层循环写成了倒序语义退化成了 01 背包。排查方法很简单随便构造一个物品体积能被容量整除的用例比如 W10、物品 w2、v3正确答案应该是 dp[10]15五件。如果你跑出来是 3基本就锁定是循环方向问题。看一眼for (int j W; j w[i]; j--)这行把它改成for (int j w[i]; j W; j)就行。4.2 二维转移写成 dp[i-1][j-w] 导致退化另一个隐蔽的坑在二维写法里把dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])写成了dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。这同样是退化成了 01 背包的转移。区别只在下标里的 i 和 i-1肉眼极难发现但语义完全不同。记住完全背包取完一件还留在本层所以是dp[i][...]01 背包取完退回上一层所以是dp[i-1][...]。4.3 初始化不当导致的“恰好装满”错误症状是恰好装满的题里答案偏大或者根本给不出正确的最大值。检查两点一是 dp[0] 有没有设成 0二是 dp[1..W] 有没有设成负无穷。如果用的是INT_MIN还要小心加 v[i] 时溢出最好用一个足够小但不至于溢出的值比如-1e9。4.4 常见问题速查表现象可能原因排查/修复答案偏小像每件只用一次内层循环倒序改为正序j: w[i] → W二维转移后答案退化写成dp[i-1][j-w]改成dp[i][j-w]恰好装满题答案错误初始化没设负无穷dp[0]0其余负无穷大容量超时用了 k 层枚举折叠为dp[j-w]v数组越界j 从 0 开始循环j 从 w[i] 开始多组数据互相污染dp 数组没重置每组数据前清零4.5 几个能提速的常数级优化虽然完全背包已经是 O(N·W)但在数据量大的时候还能再抠一点去掉“体积大且价值低”的冗余物品。如果存在物品 a 和物品 b满足 w[a] ≥ w[b] 且 v[a] ≤ v[b]那么物品 a 永远不会出现在最优解里因为拿一件 a 不如拿一件 b还省空间而 b 可以无限拿。预处理时可以 O(N²) 筛一遍。合并同体积物品同体积只保留价值最大的那件。按体积排序后处理能在局部提升缓存命中率虽然理论复杂度不变但实测在小数据上有百分之十几的提速。这些优化不是必须的但如果你在刷那种卡常数的大数据题值得加上。5. 从完全背包延伸到多重背包的思路理解了完全背包的“正序遍历”和“子问题折叠”多重背包每种物品最多取 s[i] 次就有了自然的过渡路径。多重背包不能直接套完全背包的模板因为数量有了上限当剩余件数用完后就不能再取了。最朴素的思路是把第 i 种物品当成 s[i] 个独立的 01 背包物品逐个用倒序遍历处理复杂度是 O(W·Σs[i])s[i] 大时会超时。改进版是二进制拆分把 s[i] 拆成 1、2、4、8……这些 2 的幂次最后不足的部分单独作为一块。这样每件物品被拆成 O(log s[i]) 个 01 背包物品复杂度降到 O(W·Σlog s[i])非常实用。还有一个更高级的单调队列优化把多重背包压到 O(N·W)但推导复杂属于竞赛进阶内容。我这里提它的目的是让你看到完全背包是背包体系里承上启下的一环——它上承 01 背包的“选或不选”下启多重背包的“数量限制”。把完全背包的正序原理吃透多重背包的二进制拆分会顺很多。不同的场景对应不同的变体简单的对照如下背包类型每件可取次数一维内层循环方向核心转移01 背包0 或 1 次倒序dp[j-w] v 用旧值完全背包无限次正序dp[j-w] v 用新值多重背包最多 s 次拆分后倒序二进制拆成 01这张表把我当年啃背包九讲时记得最头疼的三个方向问题一次性摆平了。如果你能默写出来说明背包的基础框架已经立住了。我个人在实际写题和给学弟讲题的过程中最大的体会是完全背包的“一维正序”这个点光看文字说明很难真正内化必须自己拿张纸把 dp 数组一步步填出来看着dp[j-w]从旧值变成新值的那一刻你才会真的记住。踩过几次“倒序写反了、答案凭空少一半”的坑之后这个方向就再也忘不掉了。另外一个建议是别一上来就背模板先把二维的朴素转移写对再自己动手压一维压缩过程中卡在哪一步那个点就是你没真正理解的地方针对性补一下就通透了。至于后续想继续深入的话可以从带着“物品至少取一次”限制的变体入手或者去研究多重背包的单调队列写法都是很自然的下一步。