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' = k+1，则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]的枚举版本，它等于“k=0的情况（即dp[i-1][j]）并上所有k>=1的情况的最大值”，而右边正好就是所有k>=1的情况的最大值。于是：
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增大到j+w[i]时，dp[(j+w[i])-w[i]]就是刚才更新过的那个值，于是dp[j+w[i]]会再次用“已经取了第i种物品”的旧状态去叠加一件，得到相当于“取两件第i种物品”的总价值。这个过程在循环中持续传播，直到容量耗尽。
这就是“一件物品被反复取”在代码层面的具象表达。正序枚举在这里扮演的角色，就是允许同一轮循环里“信息向后传递”。如果逆序枚举，信息只能“向前传递”，第i种物品永远只被使用一次，问题就退化成0-1背包了。这也是常见的题解里说“把0-1背包的j循环倒过来就是完全背包”的原因。
4.4 关于“恰好装满”的初始化细节
用一维数组实现时，初始化的方式直接影响语义。常见的有两种设定：
- “不超过容量C”：
dp[0..C]全部初始化为0。表示任何容量下都不取物品时价值也是0，然后逐步填充。 - “恰好装满容量C”：
dp[0]=0，dp[1..C]=-∞（或者一个很小的负数如-1e9）。表示除了容量0以外，“没装满”的状态是不合法的。转移时只有从合法状态（不为负无穷）转移过来才算数。
很多人在做“凑零钱”“最少硬币数”这类题时困惑为什么答案总是不对，十有八九是初始化语义搞错了。以最小硬币数问题为例，如果求的是“恰好凑出金额n”，就必须用dp[0]=0、其余为+∞（正无穷）的初始化；如果求的是“不超过金额n的最小硬币数”，那dp全部初始化为0反而合理。不要小看这个细节，它在完全背包里比在0-1背包里更容易踩，因为“无限次取用”会让错误初始化的结果偏差更大。
5. 实操演示：从一个具体例子走完完整推导
理论讲再多，不如把表格拉一遍。我们来看一个非常简单的例子，用手工推导验证方程是否正确。
假设背包容量C=10，有3种物品：
| 物品编号 | 重量w | 价值v |
|---|---|---|
| 0 | 3 | 7 |
| 1 | 4 | 5 |
| 2 | 2 | 3 |
目标是求最大价值。
第一步：初始化dp[0..10]=0。
第二步：外层循环物品0（w=3, v=7），内层j从3到10正序更新矩阵状态（这里展示完整二维表便于观察）：
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 初始 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 物品0后 | 0 | 0 | 0 | 7 | 7 | 7 | 14 | 14 | 14 | 21 | 21 |
可以看到，j每越过一个w=3的倍数，价值就多加一个7。j=6时，可以先装两件物品0（2×3=6），价值14；j=9是三件，价值21；j=10时只能装三件（9），剩容量1没法利用，价值还是21。
第三步：外层循环物品1（w=4, v=5）。j从4开始正序更新：
j=4：dp[4]=max(7, 0+5)=7，不取物品1。j=5：dp[5]=max(7, 1+5)=7，不取。j=6：dp[6]=max(14, 2+5)=14，不取。j=7：dp[7]=max(14, 3+5)=14，不取。j=8：dp[8]=max(14, 4+5)=14，不取。注意这里dp[4]是7，dp[4]+5=12，小于14。j=9：dp[9]=max(21, 5+5)=21，不取。j=10：dp[10]=max(21, 6+5)=21，不取。dp[6]是14，14+5=19，小于21。
物品1整轮跑完，dp表不变，因为它性价比低（5/4=1.25 < 7/3≈2.33）。
第四步：外层循环物品2（w=2, v=3）。j从2开始正序更新：
j=2：dp[2]=max(0, 0+3)=3j=3：dp[3]=max(7, 1+3)=7j=4：dp[4]=max(7, 2+3)=7。这里dp[2]=3，3+3=6，不如7。j=5：dp[5]=max(7, 3+3)=7j=6：dp[6]=max(14, 4+3)=14j=7：dp[7]=max(14, 5+3)=14j=8：dp[8]=max(14, 6+3)=14j=9：dp[9]=max(21, 7+3)=21j=10：dp[10]=max(21, 8+3)=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数组的大小应该是C+1，而不是n。有人习惯性开成物品数量大小，结果运行到j-w[i]时直接越界。这个错误在C++中尤其危险，因为不会立刻崩溃，只会悄悄读到垃圾值。建议初始化时直接声明为C+1，并把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的“手感”上了一个台阶——因为你看的已经不仅仅是这一道题，而是一整类“无界选择”问题的共同骨架。这个直觉在面试现场、比赛考场里是最值钱的。
