1. 从“背方程”到“推方程”完全背包问题的出发点和收益很多人在学动态规划时都有过这样的阶段0-1背包刚搞明白二维数组、逆序枚举、滚动数组都还会写结果一看到完全背包的状态转移方程就懵了。网上教程习惯直接把结论甩出来——dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])——然后告诉你“区别就是把0-1背包的逆序改成正序”。至于为什么正序就对、为什么第二维用的是dp[i]而不是dp[i-1]、为什么这个式子能表达“物品可以取无限次”大多数资料都一笔带过。这篇内容就是要把这条推导链路完整走一遍从问题建模、状态定义、集合划分再到方程推导、一维优化、代码实现和典型误区。适合正在学动态规划、准备算法面试或者刷题时总在背包变形题上卡壳的人。读完你不仅能记住这个方程更能在遇到“完全背包的排列组合变体”“恰好装满”“最少件数”这类题时自己把方程推出来。先说清楚完全背包到底解决什么问题给定n种物品每种物品的重量是w[i]、价值是v[i]每种物品可以取任意多件无限次现在有一个容量为C的背包问能装入的最大价值是多少。和0-1背包最本质的区别只有一句话0-1背包每件物品只有“取/不取”两种状态完全背包每件物品有“取0件、取1件、取2件……直到装不下”多种状态。就是这“多种状态”四个字让整个推导的复杂度从“要不要拿”变成了“到底拿几件”。而这个“拿几件”里隐藏着完全背包全部的关键细节。2. 状态定义与集合划分为什么dp[i][j]长这样2.1 把“前i件物品、容量j”讲透完全背包的状态定义大多长这样dp[i][j]表示“从前i种物品中选放进容量为j的背包能获得的最大价值”。注意这里用的是“前i种物品”而不是“前i件物品”。区别很微妙但很重要因为是无限次取用每“种”物品在计算过程中会反复出现所以状态里的i本质上是“物品种类的编号上限”不是“实际取出的总件数”。取出的总件数可能远大于i因为每种都可以拿多件。j是当前背包的剩余容量也可以理解成“当前子问题的背包大小”。这个定义和0-1背包一模一样好处是能直接利用子问题的最优解递归构造大问题的最优解。动态规划能成立的前提是“最优子结构”前i种物品在容量j下的最优选择一定可以由更小规模的最优选择推出来。这个性质对于完全背包是天然成立的——你拿走一件第i种物品之后剩下的问题依然是“前i种物品、容量j-w[i]的背包问题”。2.2 集合划分不数“取了多少件”只分“取不取第i种”推导状态转移方程最关键的一步不是列公式而是想清楚“当前状态下第i种物品到底处于什么位置”。我们把dp[i][j]对应的最优方案分成两个互不重叠的集合集合A最优方案中完全没取第i种物品。这时问题退化成“前i-1种物品、容量j的最优解”也就是dp[i-1][j]。集合B最优方案中至少取了一件第i种物品。这时我们确定性地拿走一件第i种物品获得价值v[i]背包剩余容量变成j-w[i]剩余的问题就是“前i种物品、容量j-w[i]的最优解”。集合B的剩余问题注意了用的还是“前i种物品”不是“前i-1种”。因为这个方案里已经取走一件第i种物品了由于每件物品无限次可取剩下还可以继续取第i种物品。这就是完全背包和0-1背包在推导上分道扬镳的那个岔路口。于是状态转移方程初步写成dp[i][j] max( dp[i-1][j], dp[i][j-w[i]] v[i] )条件自然是j w[i]当j w[i]时背包装不下第i种物品只能等于dp[i-1][j]。这个式子就是完全背包状态转移方程的“原始形态”。你可能会觉得它不够厚道明明说好第i种物品可以取“0件、1件、2件……无数件”这个方程里怎么只出现了dp[i-1][j]和dp[i][j-w[i]]v[i]两项“取2件”“取3件”去哪了答案藏在dp[i][j-w[i]]自身的定义里。我们展开dp[i][j-w[i]]它在做决策时同样面临第i种物品取不取的问题——如果取就进入dp[i][j-2*w[i]] v[i]不取就是dp[i-1][j-w[i]]。换句话说dp[i][j-w[i]]这个“子问题的最优解”里已经包含了“取第i种物品0次、1次、2次……直到容量不够”的所有情况。当我们把dp[i][j-w[i]]v[i]作为dp[i][j]的一个候选时本质上是在循环迭代中让“取多件”的情况被逐层传递了下去。这就是完全背包的精髓表面上只写了“取1件”的转移实际上靠着dp[i][...]的自引用把“取2件、取3件……取k件”的所有可能性都递归地折叠进了这一个方程里。不需要显式地枚举k也不需要开三维数组去记录具体件数。2.3 和0-1背包方程的对照一个下标之差0-1背包的状态转移方程是dp[i][j] max( dp[i-1][j], dp[i-1][j-w[i]] v[i] )对照一下就能发现完全背包和0-1背包的方程长得几乎一样只有第二项的前一个下标不同0-1背包是dp[i-1][j-w[i]]完全背包是dp[i][j-w[i]]。这个下标差异不是随意的“风格选择”而是对应着两种完全不同的决策逻辑0-1背包里取了这件物品它就被“消耗”了以后不能再取所以回到i-1。完全背包里取了这件物品它还在“货架”上以后还能再取所以回到i。如果你正在从0-1背包向完全背包过渡最容易犯的错误就是把这个下标写错。写错之后程序不会立刻崩溃只会给出错误的答案——因为你一不小心就把它变成了另一个问题。3. 数学化推导从枚举k到方程成形3.1 暴力枚举版本是怎么写的前面我们说方程里不需要显式枚举k但为了理解方程的正确性先看看“暴力枚举”版本的方程长什么样。这是很多人第一次接触完全背包时最直观的写法dp[i][j] max( dp[i-1][j], dp[i-1][j-w[i]] v[i], dp[i-1][j-2*w[i]] 2*v[i], dp[i-1][j-3*w[i]] 3*v[i], ... )这个式子直白地表达了一个思想第i种物品我可以取0件、1件、2件……对所有可能取的数量k满足k*w[i] j计算对应的总价值再取最大值。写成数学归纳形式就是dp[i][j] max_{k 0, k*w[i] j} ( dp[i-1][j-k*w[i]] k*v[i] )这个方程虽然“正确”但时间复杂度是O(n*C^2)级别的——每种物品对每种容量都要额外枚举一个k。当物品种类和背包容量都在几千量级时这个复杂度完全没法用。你要刷LeetCode、搞竞赛、应对面试这个版本只能用作推导的中间跳板不能作为最终实现。3.2 从枚举版本“压”出最终方程现在我们从枚举版本出发做一个数学变形。先把j固定为当前容量来看dp[i][j]和dp[i][j-w[i]]的关系。dp[i][j-w[i]]按照枚举版本展开是dp[i][j-w[i]] max_{k 0, k*w[i] j-w[i]} ( dp[i-1][j-w[i]-k*w[i]] k*v[i] )令k k1则k k-1上面的式子变成max_{k 1, k*w[i] j} ( dp[i-1][j-k*w[i]] (k-1)*v[i] )两边同时加上v[i]得到dp[i][j-w[i]] v[i] max_{k 1, k*w[i] j} ( dp[i-1][j-k*w[i]] k*v[i] )对比dp[i][j]的枚举版本它等于“k0的情况即dp[i-1][j]并上所有k1的情况的最大值”而右边正好就是所有k1的情况的最大值。于是dp[i][j] max( dp[i-1][j], dp[i][j-w[i]] v[i] )这个变形过程如果你第一次看觉得头大完全正常。我当年也是盯着纸看了好半天才转过弯来。简单记住一句话dp[i][j-w[i]] v[i]里那个dp[i]已经替你枚举过了所有“再取一件”的情况你不需要在外面再套一层循环。用生活化的类比来说dp[i][j]就像你在自助餐档口排队。你已经知道“走到这个档口前前i-1种食物能吃到的最大饱腹值”是dp[i-1][j]。现在你决定要不要拿一份当前档口的食物。拿了之后你还在这个档口排着队——只是手里的盘子容量变小了w[i]但你完全还可以再拿一份。dp[i][j-w[i]]就是“盘子变小之后站在同一个档口前你最优能拿多少”它是递归的、可以不断往后传递的。3.3 为什么“完全背包”也叫“无限背包”理解了枚举版本的压缩过程你就能体会到为什么完全背包英文里叫Unbounded Knapsack直译就是“无界背包”。这里的“无界”不是容量无界而是每种物品的件数无界。正因为件数无界dp[i][j]才敢于继续引用dp[i][j-w[i]]而不必担心“第i种物品会不会已经被用完”。这个“无界”特性也是后续所有优化技巧的出发点。如果题目改成“每种物品最多取m[i]件”那就是多重背包问题方程又会完全变样——因为那时dp[i][j]不能随便引用dp[i][j-w[i]]了必须加上件数约束。推导完全背包方程的价值不只是解决这一道题更是为你理解多重背包的“二进制拆分优化”打底子。4. 一维滚动数组优化正序枚举的根源4.1 降维的标准操作现在我们已经有了二维版本的方程dp[i][j] max( dp[i-1][j], dp[i][j-w[i]] v[i] )观察这个方程dp[i]这一层在计算时只用到了dp[i-1]上一层的容量j和dp[i]当前层的更小容量。既然只依赖“上一层同容量”和“当前层较小容量”那就可以把第一维的空间省略掉只保留一个一维数组dp[j]。问题来了二维降到一维之后枚举顺序怎么定在0-1背包的滚动数组版本里容量j必须从大到小逆序枚举。原因是0-1背包的dp[i][j]依赖dp[i-1][j-w[i]]如果正序更新dp[j]那么更新dp[j]时dp[j-w[i]]可能已经被本轮循环改成了dp[i][j-w[i]]——也就是“已经取过这件物品”的状态这就违反了0-1背包“每件最多取一次”的规则。但在完全背包里我们本来就要dp[i][j-w[i]]也就是“当前轮已经取过第i种物品、还可以再取”的状态。所以完全背包的容量枚举必须正序才能让新的dp[j-w[i]]被及时用于计算更大的dp[j]。这就是网上流传的“0-1背包逆序、完全背包正序”口诀的真正原因。它不是凭空记住的规则而是直接由状态转移方程中dp[i]和dp[i-1]的下标差异决定的。4.2 一维完全背包的最终形态降维后的完全背包代码如下for (int i 0; i n; i) { for (int j w[i]; j C; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }每一行拆开看for (int i 0; i n; i)外层循环枚举物品种类。顺序无所谓?不对不能随便说顺序无所谓。对于完全背包的组合问题每种物品无限取求最大价值物品种类的循环顺序确实不影响最终最大价值因为“取哪些种、各取多少”是集合关系。但对于某些变形题比如求“恰好装满的方案数”且认为“先取A再取B”和“先取B再取A”是不同方案时外层循环顺序就会影响结果。这个坑后面专门讲。for (int j w[i]; j C; j)容量正序递增。这里从w[i]开始因为小于w[i]的容量根本放不下第i种物品dp[j]的值不会变省去无意义的赋值。dp[j] max(dp[j], dp[j - w[i]] v[i])dp[j]在这个时刻代表“在前i种物品中选、容量j的最大价值”。为什么要用max而不是直接赋值因为要保留“不取第i种物品”时的旧值dp[i-1][j]。用Python写则更简洁逻辑完全一致for i in range(n): for j in range(w[i], C 1): dp[j] max(dp[j], dp[j - w[i]] v[i])4.3 为什么要拿dp[j-w[i]]当“本次更新的依据”接前面说的dp[j-w[i]]在一维数组中是什么时候被更新的它是被当前第i轮循环更新过的前提是j-w[i] w[i]即能放下第二件。想象一下整个流程第一件第i种物品被放入后dp[j]被更新为dp[j-w[i]]v[i]。接着当j增大到jw[i]时dp[(jw[i])-w[i]]就是刚才更新过的那个值于是dp[jw[i]]会再次用“已经取了第i种物品”的旧状态去叠加一件得到相当于“取两件第i种物品”的总价值。这个过程在循环中持续传播直到容量耗尽。这就是“一件物品被反复取”在代码层面的具象表达。正序枚举在这里扮演的角色就是允许同一轮循环里“信息向后传递”。如果逆序枚举信息只能“向前传递”第i种物品永远只被使用一次问题就退化成0-1背包了。这也是常见的题解里说“把0-1背包的j循环倒过来就是完全背包”的原因。4.4 关于“恰好装满”的初始化细节用一维数组实现时初始化的方式直接影响语义。常见的有两种设定“不超过容量C”dp[0..C]全部初始化为0。表示任何容量下都不取物品时价值也是0然后逐步填充。“恰好装满容量C”dp[0]0dp[1..C]-∞或者一个很小的负数如-1e9。表示除了容量0以外“没装满”的状态是不合法的。转移时只有从合法状态不为负无穷转移过来才算数。很多人在做“凑零钱”“最少硬币数”这类题时困惑为什么答案总是不对十有八九是初始化语义搞错了。以最小硬币数问题为例如果求的是“恰好凑出金额n”就必须用dp[0]0、其余为∞正无穷的初始化如果求的是“不超过金额n的最小硬币数”那dp全部初始化为0反而合理。不要小看这个细节它在完全背包里比在0-1背包里更容易踩因为“无限次取用”会让错误初始化的结果偏差更大。5. 实操演示从一个具体例子走完完整推导理论讲再多不如把表格拉一遍。我们来看一个非常简单的例子用手工推导验证方程是否正确。假设背包容量C10有3种物品物品编号重量w价值v037145223目标是求最大价值。第一步初始化dp[0..10]0。第二步外层循环物品0w3, v7内层j从3到10正序更新矩阵状态这里展示完整二维表便于观察j012345678910初始00000000000物品0后0007771414142121可以看到j每越过一个w3的倍数价值就多加一个7。j6时可以先装两件物品02×36价值14j9是三件价值21j10时只能装三件9剩容量1没法利用价值还是21。第三步外层循环物品1w4, v5。j从4开始正序更新j4dp[4]max(7, 05)7不取物品1。j5dp[5]max(7, 15)7不取。j6dp[6]max(14, 25)14不取。j7dp[7]max(14, 35)14不取。j8dp[8]max(14, 45)14不取。注意这里dp[4]是7dp[4]512小于14。j9dp[9]max(21, 55)21不取。j10dp[10]max(21, 65)21不取。dp[6]是1414519小于21。物品1整轮跑完dp表不变因为它性价比低5/41.25 7/3≈2.33。第四步外层循环物品2w2, v3。j从2开始正序更新j2dp[2]max(0, 03)3j3dp[3]max(7, 13)7j4dp[4]max(7, 23)7。这里dp[2]3336不如7。j5dp[5]max(7, 33)7j6dp[6]max(14, 43)14j7dp[7]max(14, 53)14j8dp[8]max(14, 63)14j9dp[9]max(21, 73)21j10dp[10]max(21, 83)21最终dp[10]21具体方案是3件物品0刚好9重量价值21。手工推一遍的价值在于你能亲眼看到“正序更新”是如何让物品0的价值在容量6、9处叠加的也能看到性价比低的物品如何被max自然淘汰。动手推过一次之后方程就不再是个需要死记的公式了。6. 常见误区与排查技巧实录6.1 误写成逆序变成0-1背包这是最常见、也最隐蔽的错误。把内层循环从for (int j w[i]; j C; j)改成for (int j C; j w[i]; j--)代码形式上完全合法编译器也不会报错但结果就完全错了——你求解的实际上是“每种物品最多取一件”的0-1背包。排查技巧用前面的手工例子验证。0-1背包对物品0的dp表是0 0 0 7 7 7 7 7 7 7 7最多取一件而完全背包是0 0 0 7 7 7 14 14 14 21 21。如果跑出来的结果和前者一致说明你的内层循环方向写反了。6.2dp[j-w[i]]被污染不那是特性不是bug有些从0-1背包转过来的人会怀疑正序枚举时dp[j-w[i]]已经包含了当前物品的信息再用它来更新dp[j]会不会导致同一件物品被重复计算的次数超出实际约束在完全背包里这个“污染”正是我们要的。但如果你跑的是多重背包每种物品有数量上限就必须用0-1背包的逆序思路再加一层件数控制不能直接套完全背包。建议在代码注释里明确写清楚你用的是哪个背包模型否则过两周回来看代码很容易精神分裂。6.3 外层循环物品、内层循环容量的语义影响前面提过完全背包求“最大价值”时外层循环物品还是外层循环容量都不影响最终的最大价值。但对“方案数”或“组合顺序”类问题就不一样了。举个例子LeetCode的“零钱兑换II”求的是“凑出金额的组合数”它要求外层循环硬币、内层循环金额这样得到的是不考虑顺序的组合数如果把两层循环交换得到的就是考虑顺序的排列数结果会大得多。很多人在做这类变形题时忘了这个区别明明代码逻辑看起来“一模一样”输出却不对。本质原因就藏在完全背包方程推导中的那个dp[i][j-w[i]]里——i作为物品种类编号它的循环顺序决定了每种物品之间是“并列选择”还是“可以交错挑选”。6.4 数组容量开多大背包问题里dp数组的大小应该是C1而不是n。有人习惯性开成物品数量大小结果运行到j-w[i]时直接越界。这个错误在C中尤其危险因为不会立刻崩溃只会悄悄读到垃圾值。建议初始化时直接声明为C1并把dp[0]单独确认好初值。6.5 价值可能为负时怎么办如果物品的价值v[i]可能是负数dp[j]的最优值就不一定来自“尽量多取”方程中的max逻辑仍然成立但初始化细节要更小心。实际比赛中这个场景比较少见不过一旦遇到直接取-1e9作为无效值是最稳妥的。6.6 重量为0的物品死循环炸弹完全背包中如果存在w[i]0且v[i]0的物品正序循环会无限循环或者实际运行中疯狂加价值直到溢出。这是因为j-w[i]j更新dp[j]时引用的还是dp[j]自己再加上v[i]导致每轮都把价值无限放大。如果题目没明确说重量为正务必在代码开头做一个防御性判断或者提前过滤掉这类物品。刷题时可能不太碰到但工程化实现时这个边界条件一定要处理。7. 延伸思考一个方程衍生出的变体题完全背包的状态转移方程推导清楚之后可以顺手解决很多看起来完全不像背包的题目。这里列举几个我实际遇到过的“亲兄弟”题目帮你建立一个模式识别的概念“零钱兑换”给定硬币面额和总金额求最少硬币数。把重量对应面额、价值对应1或-1目标从“最大价值”换成“最小数量”即可。转移方程变成dp[j] min(dp[j], dp[j-w[i]] 1)。“零钱兑换II”求凑出总金额的方案总数。转移方程变成dp[j] dp[j] dp[j-w[i]]外层硬币、内层金额才能保证组合数而不是排列数。“单词拆分”给定字符串和字典问能否拆分成字典中的单词。这是完全背包的字符串版每个单词可以反复使用但拼接顺序有讲究细节比传统背包再复杂一些。“整数拆分/剪绳子”把整数拆成若干个正整数的和求最大乘积。本质上也是完全背包思想只是把“容量”换成了“数值”“价值”换成了“乘积”。这些题的代码框架和完全背包高度相似区别往往只在目标函数是max还是min、初始化值、外层循环顺序这三个点。理解了方程推导而不是只背模板遇到这类变体时才能快速反应出正确的代码形态。我个人在实际学习中的体会是完全背包这个推导过程值得在纸上完整推两遍。第一遍跟着文章推第二遍合上文章自己推。推完之后再去做三五道变体题你会明显感觉到对DP的“手感”上了一个台阶——因为你看的已经不仅仅是这一道题而是一整类“无界选择”问题的共同骨架。这个直觉在面试现场、比赛考场里是最值钱的。 
长河君 · 2026/10/1 11:58:43 · 阅读 1.2k 完全背包问题详解：从状态转移方程推导到正序枚举实现
1. 从“背方程”到“推方程”完全背包问题的出发点和收益很多人在学动态规划时都有过这样的阶段0-1背包刚搞明白二维数组、逆序枚举、滚动数组都还会写结果一看到完全背包的状态转移方程就懵了。网上教程习惯直接把结论甩出来——dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])——然后告诉你“区别就是把0-1背包的逆序改成正序”。至于为什么正序就对、为什么第二维用的是dp[i]而不是dp[i-1]、为什么这个式子能表达“物品可以取无限次”大多数资料都一笔带过。这篇内容就是要把这条推导链路完整走一遍从问题建模、状态定义、集合划分再到方程推导、一维优化、代码实现和典型误区。适合正在学动态规划、准备算法面试或者刷题时总在背包变形题上卡壳的人。读完你不仅能记住这个方程更能在遇到“完全背包的排列组合变体”“恰好装满”“最少件数”这类题时自己把方程推出来。先说清楚完全背包到底解决什么问题给定n种物品每种物品的重量是w[i]、价值是v[i]每种物品可以取任意多件无限次现在有一个容量为C的背包问能装入的最大价值是多少。和0-1背包最本质的区别只有一句话0-1背包每件物品只有“取/不取”两种状态完全背包每件物品有“取0件、取1件、取2件……直到装不下”多种状态。就是这“多种状态”四个字让整个推导的复杂度从“要不要拿”变成了“到底拿几件”。而这个“拿几件”里隐藏着完全背包全部的关键细节。2. 状态定义与集合划分为什么dp[i][j]长这样2.1 把“前i件物品、容量j”讲透完全背包的状态定义大多长这样dp[i][j]表示“从前i种物品中选放进容量为j的背包能获得的最大价值”。注意这里用的是“前i种物品”而不是“前i件物品”。区别很微妙但很重要因为是无限次取用每“种”物品在计算过程中会反复出现所以状态里的i本质上是“物品种类的编号上限”不是“实际取出的总件数”。取出的总件数可能远大于i因为每种都可以拿多件。j是当前背包的剩余容量也可以理解成“当前子问题的背包大小”。这个定义和0-1背包一模一样好处是能直接利用子问题的最优解递归构造大问题的最优解。动态规划能成立的前提是“最优子结构”前i种物品在容量j下的最优选择一定可以由更小规模的最优选择推出来。这个性质对于完全背包是天然成立的——你拿走一件第i种物品之后剩下的问题依然是“前i种物品、容量j-w[i]的背包问题”。2.2 集合划分不数“取了多少件”只分“取不取第i种”推导状态转移方程最关键的一步不是列公式而是想清楚“当前状态下第i种物品到底处于什么位置”。我们把dp[i][j]对应的最优方案分成两个互不重叠的集合集合A最优方案中完全没取第i种物品。这时问题退化成“前i-1种物品、容量j的最优解”也就是dp[i-1][j]。集合B最优方案中至少取了一件第i种物品。这时我们确定性地拿走一件第i种物品获得价值v[i]背包剩余容量变成j-w[i]剩余的问题就是“前i种物品、容量j-w[i]的最优解”。集合B的剩余问题注意了用的还是“前i种物品”不是“前i-1种”。因为这个方案里已经取走一件第i种物品了由于每件物品无限次可取剩下还可以继续取第i种物品。这就是完全背包和0-1背包在推导上分道扬镳的那个岔路口。于是状态转移方程初步写成dp[i][j] max( dp[i-1][j], dp[i][j-w[i]] v[i] )条件自然是j w[i]当j w[i]时背包装不下第i种物品只能等于dp[i-1][j]。这个式子就是完全背包状态转移方程的“原始形态”。你可能会觉得它不够厚道明明说好第i种物品可以取“0件、1件、2件……无数件”这个方程里怎么只出现了dp[i-1][j]和dp[i][j-w[i]]v[i]两项“取2件”“取3件”去哪了答案藏在dp[i][j-w[i]]自身的定义里。我们展开dp[i][j-w[i]]它在做决策时同样面临第i种物品取不取的问题——如果取就进入dp[i][j-2*w[i]] v[i]不取就是dp[i-1][j-w[i]]。换句话说dp[i][j-w[i]]这个“子问题的最优解”里已经包含了“取第i种物品0次、1次、2次……直到容量不够”的所有情况。当我们把dp[i][j-w[i]]v[i]作为dp[i][j]的一个候选时本质上是在循环迭代中让“取多件”的情况被逐层传递了下去。这就是完全背包的精髓表面上只写了“取1件”的转移实际上靠着dp[i][...]的自引用把“取2件、取3件……取k件”的所有可能性都递归地折叠进了这一个方程里。不需要显式地枚举k也不需要开三维数组去记录具体件数。2.3 和0-1背包方程的对照一个下标之差0-1背包的状态转移方程是dp[i][j] max( dp[i-1][j], dp[i-1][j-w[i]] v[i] )对照一下就能发现完全背包和0-1背包的方程长得几乎一样只有第二项的前一个下标不同0-1背包是dp[i-1][j-w[i]]完全背包是dp[i][j-w[i]]。这个下标差异不是随意的“风格选择”而是对应着两种完全不同的决策逻辑0-1背包里取了这件物品它就被“消耗”了以后不能再取所以回到i-1。完全背包里取了这件物品它还在“货架”上以后还能再取所以回到i。如果你正在从0-1背包向完全背包过渡最容易犯的错误就是把这个下标写错。写错之后程序不会立刻崩溃只会给出错误的答案——因为你一不小心就把它变成了另一个问题。3. 数学化推导从枚举k到方程成形3.1 暴力枚举版本是怎么写的前面我们说方程里不需要显式枚举k但为了理解方程的正确性先看看“暴力枚举”版本的方程长什么样。这是很多人第一次接触完全背包时最直观的写法dp[i][j] max( dp[i-1][j], dp[i-1][j-w[i]] v[i], dp[i-1][j-2*w[i]] 2*v[i], dp[i-1][j-3*w[i]] 3*v[i], ... )这个式子直白地表达了一个思想第i种物品我可以取0件、1件、2件……对所有可能取的数量k满足k*w[i] j计算对应的总价值再取最大值。写成数学归纳形式就是dp[i][j] max_{k 0, k*w[i] j} ( dp[i-1][j-k*w[i]] k*v[i] )这个方程虽然“正确”但时间复杂度是O(n*C^2)级别的——每种物品对每种容量都要额外枚举一个k。当物品种类和背包容量都在几千量级时这个复杂度完全没法用。你要刷LeetCode、搞竞赛、应对面试这个版本只能用作推导的中间跳板不能作为最终实现。3.2 从枚举版本“压”出最终方程现在我们从枚举版本出发做一个数学变形。先把j固定为当前容量来看dp[i][j]和dp[i][j-w[i]]的关系。dp[i][j-w[i]]按照枚举版本展开是dp[i][j-w[i]] max_{k 0, k*w[i] j-w[i]} ( dp[i-1][j-w[i]-k*w[i]] k*v[i] )令k k1则k k-1上面的式子变成max_{k 1, k*w[i] j} ( dp[i-1][j-k*w[i]] (k-1)*v[i] )两边同时加上v[i]得到dp[i][j-w[i]] v[i] max_{k 1, k*w[i] j} ( dp[i-1][j-k*w[i]] k*v[i] )对比dp[i][j]的枚举版本它等于“k0的情况即dp[i-1][j]并上所有k1的情况的最大值”而右边正好就是所有k1的情况的最大值。于是dp[i][j] max( dp[i-1][j], dp[i][j-w[i]] v[i] )这个变形过程如果你第一次看觉得头大完全正常。我当年也是盯着纸看了好半天才转过弯来。简单记住一句话dp[i][j-w[i]] v[i]里那个dp[i]已经替你枚举过了所有“再取一件”的情况你不需要在外面再套一层循环。用生活化的类比来说dp[i][j]就像你在自助餐档口排队。你已经知道“走到这个档口前前i-1种食物能吃到的最大饱腹值”是dp[i-1][j]。现在你决定要不要拿一份当前档口的食物。拿了之后你还在这个档口排着队——只是手里的盘子容量变小了w[i]但你完全还可以再拿一份。dp[i][j-w[i]]就是“盘子变小之后站在同一个档口前你最优能拿多少”它是递归的、可以不断往后传递的。3.3 为什么“完全背包”也叫“无限背包”理解了枚举版本的压缩过程你就能体会到为什么完全背包英文里叫Unbounded Knapsack直译就是“无界背包”。这里的“无界”不是容量无界而是每种物品的件数无界。正因为件数无界dp[i][j]才敢于继续引用dp[i][j-w[i]]而不必担心“第i种物品会不会已经被用完”。这个“无界”特性也是后续所有优化技巧的出发点。如果题目改成“每种物品最多取m[i]件”那就是多重背包问题方程又会完全变样——因为那时dp[i][j]不能随便引用dp[i][j-w[i]]了必须加上件数约束。推导完全背包方程的价值不只是解决这一道题更是为你理解多重背包的“二进制拆分优化”打底子。4. 一维滚动数组优化正序枚举的根源4.1 降维的标准操作现在我们已经有了二维版本的方程dp[i][j] max( dp[i-1][j], dp[i][j-w[i]] v[i] )观察这个方程dp[i]这一层在计算时只用到了dp[i-1]上一层的容量j和dp[i]当前层的更小容量。既然只依赖“上一层同容量”和“当前层较小容量”那就可以把第一维的空间省略掉只保留一个一维数组dp[j]。问题来了二维降到一维之后枚举顺序怎么定在0-1背包的滚动数组版本里容量j必须从大到小逆序枚举。原因是0-1背包的dp[i][j]依赖dp[i-1][j-w[i]]如果正序更新dp[j]那么更新dp[j]时dp[j-w[i]]可能已经被本轮循环改成了dp[i][j-w[i]]——也就是“已经取过这件物品”的状态这就违反了0-1背包“每件最多取一次”的规则。但在完全背包里我们本来就要dp[i][j-w[i]]也就是“当前轮已经取过第i种物品、还可以再取”的状态。所以完全背包的容量枚举必须正序才能让新的dp[j-w[i]]被及时用于计算更大的dp[j]。这就是网上流传的“0-1背包逆序、完全背包正序”口诀的真正原因。它不是凭空记住的规则而是直接由状态转移方程中dp[i]和dp[i-1]的下标差异决定的。4.2 一维完全背包的最终形态降维后的完全背包代码如下for (int i 0; i n; i) { for (int j w[i]; j C; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }每一行拆开看for (int i 0; i n; i)外层循环枚举物品种类。顺序无所谓?不对不能随便说顺序无所谓。对于完全背包的组合问题每种物品无限取求最大价值物品种类的循环顺序确实不影响最终最大价值因为“取哪些种、各取多少”是集合关系。但对于某些变形题比如求“恰好装满的方案数”且认为“先取A再取B”和“先取B再取A”是不同方案时外层循环顺序就会影响结果。这个坑后面专门讲。for (int j w[i]; j C; j)容量正序递增。这里从w[i]开始因为小于w[i]的容量根本放不下第i种物品dp[j]的值不会变省去无意义的赋值。dp[j] max(dp[j], dp[j - w[i]] v[i])dp[j]在这个时刻代表“在前i种物品中选、容量j的最大价值”。为什么要用max而不是直接赋值因为要保留“不取第i种物品”时的旧值dp[i-1][j]。用Python写则更简洁逻辑完全一致for i in range(n): for j in range(w[i], C 1): dp[j] max(dp[j], dp[j - w[i]] v[i])4.3 为什么要拿dp[j-w[i]]当“本次更新的依据”接前面说的dp[j-w[i]]在一维数组中是什么时候被更新的它是被当前第i轮循环更新过的前提是j-w[i] w[i]即能放下第二件。想象一下整个流程第一件第i种物品被放入后dp[j]被更新为dp[j-w[i]]v[i]。接着当j增大到jw[i]时dp[(jw[i])-w[i]]就是刚才更新过的那个值于是dp[jw[i]]会再次用“已经取了第i种物品”的旧状态去叠加一件得到相当于“取两件第i种物品”的总价值。这个过程在循环中持续传播直到容量耗尽。这就是“一件物品被反复取”在代码层面的具象表达。正序枚举在这里扮演的角色就是允许同一轮循环里“信息向后传递”。如果逆序枚举信息只能“向前传递”第i种物品永远只被使用一次问题就退化成0-1背包了。这也是常见的题解里说“把0-1背包的j循环倒过来就是完全背包”的原因。4.4 关于“恰好装满”的初始化细节用一维数组实现时初始化的方式直接影响语义。常见的有两种设定“不超过容量C”dp[0..C]全部初始化为0。表示任何容量下都不取物品时价值也是0然后逐步填充。“恰好装满容量C”dp[0]0dp[1..C]-∞或者一个很小的负数如-1e9。表示除了容量0以外“没装满”的状态是不合法的。转移时只有从合法状态不为负无穷转移过来才算数。很多人在做“凑零钱”“最少硬币数”这类题时困惑为什么答案总是不对十有八九是初始化语义搞错了。以最小硬币数问题为例如果求的是“恰好凑出金额n”就必须用dp[0]0、其余为∞正无穷的初始化如果求的是“不超过金额n的最小硬币数”那dp全部初始化为0反而合理。不要小看这个细节它在完全背包里比在0-1背包里更容易踩因为“无限次取用”会让错误初始化的结果偏差更大。5. 实操演示从一个具体例子走完完整推导理论讲再多不如把表格拉一遍。我们来看一个非常简单的例子用手工推导验证方程是否正确。假设背包容量C10有3种物品物品编号重量w价值v037145223目标是求最大价值。第一步初始化dp[0..10]0。第二步外层循环物品0w3, v7内层j从3到10正序更新矩阵状态这里展示完整二维表便于观察j012345678910初始00000000000物品0后0007771414142121可以看到j每越过一个w3的倍数价值就多加一个7。j6时可以先装两件物品02×36价值14j9是三件价值21j10时只能装三件9剩容量1没法利用价值还是21。第三步外层循环物品1w4, v5。j从4开始正序更新j4dp[4]max(7, 05)7不取物品1。j5dp[5]max(7, 15)7不取。j6dp[6]max(14, 25)14不取。j7dp[7]max(14, 35)14不取。j8dp[8]max(14, 45)14不取。注意这里dp[4]是7dp[4]512小于14。j9dp[9]max(21, 55)21不取。j10dp[10]max(21, 65)21不取。dp[6]是1414519小于21。物品1整轮跑完dp表不变因为它性价比低5/41.25 7/3≈2.33。第四步外层循环物品2w2, v3。j从2开始正序更新j2dp[2]max(0, 03)3j3dp[3]max(7, 13)7j4dp[4]max(7, 23)7。这里dp[2]3336不如7。j5dp[5]max(7, 33)7j6dp[6]max(14, 43)14j7dp[7]max(14, 53)14j8dp[8]max(14, 63)14j9dp[9]max(21, 73)21j10dp[10]max(21, 83)21最终dp[10]21具体方案是3件物品0刚好9重量价值21。手工推一遍的价值在于你能亲眼看到“正序更新”是如何让物品0的价值在容量6、9处叠加的也能看到性价比低的物品如何被max自然淘汰。动手推过一次之后方程就不再是个需要死记的公式了。6. 常见误区与排查技巧实录6.1 误写成逆序变成0-1背包这是最常见、也最隐蔽的错误。把内层循环从for (int j w[i]; j C; j)改成for (int j C; j w[i]; j--)代码形式上完全合法编译器也不会报错但结果就完全错了——你求解的实际上是“每种物品最多取一件”的0-1背包。排查技巧用前面的手工例子验证。0-1背包对物品0的dp表是0 0 0 7 7 7 7 7 7 7 7最多取一件而完全背包是0 0 0 7 7 7 14 14 14 21 21。如果跑出来的结果和前者一致说明你的内层循环方向写反了。6.2dp[j-w[i]]被污染不那是特性不是bug有些从0-1背包转过来的人会怀疑正序枚举时dp[j-w[i]]已经包含了当前物品的信息再用它来更新dp[j]会不会导致同一件物品被重复计算的次数超出实际约束在完全背包里这个“污染”正是我们要的。但如果你跑的是多重背包每种物品有数量上限就必须用0-1背包的逆序思路再加一层件数控制不能直接套完全背包。建议在代码注释里明确写清楚你用的是哪个背包模型否则过两周回来看代码很容易精神分裂。6.3 外层循环物品、内层循环容量的语义影响前面提过完全背包求“最大价值”时外层循环物品还是外层循环容量都不影响最终的最大价值。但对“方案数”或“组合顺序”类问题就不一样了。举个例子LeetCode的“零钱兑换II”求的是“凑出金额的组合数”它要求外层循环硬币、内层循环金额这样得到的是不考虑顺序的组合数如果把两层循环交换得到的就是考虑顺序的排列数结果会大得多。很多人在做这类变形题时忘了这个区别明明代码逻辑看起来“一模一样”输出却不对。本质原因就藏在完全背包方程推导中的那个dp[i][j-w[i]]里——i作为物品种类编号它的循环顺序决定了每种物品之间是“并列选择”还是“可以交错挑选”。6.4 数组容量开多大背包问题里dp数组的大小应该是C1而不是n。有人习惯性开成物品数量大小结果运行到j-w[i]时直接越界。这个错误在C中尤其危险因为不会立刻崩溃只会悄悄读到垃圾值。建议初始化时直接声明为C1并把dp[0]单独确认好初值。6.5 价值可能为负时怎么办如果物品的价值v[i]可能是负数dp[j]的最优值就不一定来自“尽量多取”方程中的max逻辑仍然成立但初始化细节要更小心。实际比赛中这个场景比较少见不过一旦遇到直接取-1e9作为无效值是最稳妥的。6.6 重量为0的物品死循环炸弹完全背包中如果存在w[i]0且v[i]0的物品正序循环会无限循环或者实际运行中疯狂加价值直到溢出。这是因为j-w[i]j更新dp[j]时引用的还是dp[j]自己再加上v[i]导致每轮都把价值无限放大。如果题目没明确说重量为正务必在代码开头做一个防御性判断或者提前过滤掉这类物品。刷题时可能不太碰到但工程化实现时这个边界条件一定要处理。7. 延伸思考一个方程衍生出的变体题完全背包的状态转移方程推导清楚之后可以顺手解决很多看起来完全不像背包的题目。这里列举几个我实际遇到过的“亲兄弟”题目帮你建立一个模式识别的概念“零钱兑换”给定硬币面额和总金额求最少硬币数。把重量对应面额、价值对应1或-1目标从“最大价值”换成“最小数量”即可。转移方程变成dp[j] min(dp[j], dp[j-w[i]] 1)。“零钱兑换II”求凑出总金额的方案总数。转移方程变成dp[j] dp[j] dp[j-w[i]]外层硬币、内层金额才能保证组合数而不是排列数。“单词拆分”给定字符串和字典问能否拆分成字典中的单词。这是完全背包的字符串版每个单词可以反复使用但拼接顺序有讲究细节比传统背包再复杂一些。“整数拆分/剪绳子”把整数拆成若干个正整数的和求最大乘积。本质上也是完全背包思想只是把“容量”换成了“数值”“价值”换成了“乘积”。这些题的代码框架和完全背包高度相似区别往往只在目标函数是max还是min、初始化值、外层循环顺序这三个点。理解了方程推导而不是只背模板遇到这类变体时才能快速反应出正确的代码形态。我个人在实际学习中的体会是完全背包这个推导过程值得在纸上完整推两遍。第一遍跟着文章推第二遍合上文章自己推。推完之后再去做三五道变体题你会明显感觉到对DP的“手感”上了一个台阶——因为你看的已经不仅仅是这一道题而是一整类“无界选择”问题的共同骨架。这个直觉在面试现场、比赛考场里是最值钱的。