刷动态规划题的时候，十个新手里有八个会卡在完全背包的状态转移方程上。我自己当年也是这样：盯着dp[i][j] = max(dp[i-1][j], dp[i][j - v[i]] + w[i])这行代码看了半天，死活想不明白为什么第二项的下标从i-1变成了i，更想不通为什么代码里一维数组的循环方向从“逆序”变成了“正序”。后来我把整个推导过程完完整整推了一遍，才意识到这背后藏着一个非常优雅的等价替换——完全背包的状态转移方程并不是凭空给出的，它是从最朴素的“枚举第 i 种物品选几件”的写法，一步步化简、消元得来的。这篇文章就把这条推导路径完整拆开，顺便把一维优化为什么是正序这件事讲到透。无论你是刚开始学背包问题的新手，还是刷题遇到变体想回头补原理的老手，这篇都值得花十分钟读一遍。
1. 从 01 背包到完全背包：先把问题定义清楚
1.1 问题描述与符号约定
完全背包问题的标准描述是：有一个容量为V的背包，有N种物品，第i种物品的体积是v[i]，价值是w[i]，每种物品都有无限件可用。问在不超过背包容量的前提下，能装入的最大总价值是多少。
这里最关键的一个词就是“无限件”。01 背包里每个物品要么拿要么不拿，最多只能拿一件；完全背包里第i种物品你可以拿 0 件、1 件、2 件……一直拿到容量装不下为止。
为了讨论方便，先约定 DP 状态：
dp[i][j]表示：考虑前i种物品，背包容量为j时，能获得的最大价值。- 其中
1 <= i <= N，0 <= j <= V。
这个状态定义和 01 背包完全一致。因为 DP 方程的推导本质上就是在回答一个问题：当决策到第i种物品、手里剩下容量j时，这个格子dp[i][j]该怎么从前面的状态递推过来。
1.2 和 01 背包的本质差异
很多人上来就背代码，只知道“01 逆序、完全正序”，却不知道这个差异的根源。根源就一句话：01 背包的状态转移依赖的是“上一行”的数据，完全背包的状态转移依赖的是“当前行”的数据。
| 对比项 | 01 背包 | 完全背包 |
|---|---|---|
| 每种物品可选次数 | 0 或 1 次 | 0 次或任意多次 |
| 二维状态转移 | dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]) | dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i]) |
| 内层一维循环方向 | 从V到v[i]（逆序） | 从v[i]到V（正序） |
| 依赖的数据来源 | 上一行，即“还没考虑当前物品”的状态 | 当前行，即“已经可能取过当前物品”的状态 |
一个依赖上一行，一个依赖当前行，这就是所有表象差异的总根源。后面我们会看到，这个差异不是靠记忆“正序逆序”这种口诀就能完全理解的，必须落到状态转移方程本身。
2. 状态转移方程的完整推导：从枚举到消元
2.1 第一版推导：枚举第 i 种物品选几件
最直观的思考方式是把第i种物品的决策拆开：它到底选几件？假设选了k件（k >= 0），那么这k件物品占用的体积是k * v[i]，贡献的价值是k * w[i]，剩下的容量j - k * v[i]必须由前i-1种物品来填充，这部分的最高价值就是dp[i-1][j - k*v[i]]。
于是可以得到完全背包的“原始方程”：
dp[i][j] = max_{k=0,1,2,...} ( dp[i-1][j - k*v[i]] + k*w[i] )这里的k必须满足k*v[i] <= j，也就是说第i种物品不能塞超容量。
这个方程是正确且完备的，因为k的枚举确实覆盖了所有可能选择第i种物品的数量。但它有个致命问题：每算一个格子都要枚举k，而k的上限可以到j / v[i]，所以整体复杂度是O(N * V * V)级别。当背包容量V是几千几万时，这个复杂度会直接爆炸。
举个例子，容量V = 10000，只有 100 种物品，按这个朴素方程算，最坏情况下状态数是100 * 10001 ≈ 10^6，但每个格子的k可能枚举几百次，总操作量瞬间上亿，很多题目就直接超时。
所以必须想办法把k这一层枚举消掉。怎么消？答案藏在展开式里。
2.2 经典消元推导：用 dp[i][j-v[i]] 代换展开式
把上面的式子按k的值展开，能看得更清楚：
dp[i][j] = max( dp[i-1][j], dp[i-1][j - v[i]] + w[i], dp[i-1][j - 2*v[i]] + 2*w[i], dp[i-1][j - 3*v[i]] + 3*w[i], ... )第一项是k=0，也就是完全不取第i种物品；第二项是k=1，取 1 件；第三项是k=2，取 2 件；依此类推。
现在再观察另一个格子：dp[i][j - v[i]]。它同样写成展开式：
dp[i][j - v[i]] = max( dp[i-1][j - v[i]], dp[i-1][j - 2*v[i]] + w[i], dp[i-1][j - 3*v[i]] + 2*w[i], dp[i-1][j - 4*v[i]] + 3*w[i], ... )注意，这个展开式和dp[i][j]的展开式很像，只是每一项都“少了一件第i种物品”的体量和价值。
两边同时加上一个w[i]：
dp[i][j - v[i]] + w[i] = max( dp[i-1][j - v[i]] + w[i], dp[i-1][j - 2*v[i]] + 2*w[i], dp[i-1][j - 3*v[i]] + 3*w[i], ... )现在把dp[i][j]的展开式和上面的等式放在一起对照：
dp[i][j]的展开式里，除了第一项dp[i-1][j]之外，其余所有项分别是：dp[i-1][j-v[i]] + w[i]、dp[i-1][j-2*v[i]] + 2*w[i]、dp[i-1][j-3*v[i]] + 3*w[i]……- 而
dp[i][j-v[i]] + w[i]展开后，恰好就是这一串：dp[i-1][j-v[i]] + w[i]、dp[i-1][j-2*v[i]] + 2*w[i]、dp[i-1][j-3*v[i]] + 3*w[i]……
完全对应。于是得到最终的状态转移方程：
dp[i][j] = max( dp[i-1][j], dp[i][j-v[i]] + w[i] )这一手“用低容量状态代换长展开式”的化简，就是完全背包状态转移方程推导中最核心的步骤。它告诉我们：取多件第i种物品的情况，不需要每次重新枚举，而是可以通过“在容量j-v[i]的当前最优状态上，再放 1 件第i种物品”来递推。
2.3 集合划分视角：选 0 件 vs 至少选 1 件
除了用展开式消元，另一个非常直观的理解方式是从集合划分的角度切入。
面对第i种物品，任何方案都可以分成两类：
- 完全不选第
i种物品。此时价值就是dp[i-1][j]。 - 至少选 1 件第
i种物品。那不妨先强制取 1 件，花掉体积v[i]、拿到价值w[i]，剩下来的容量j - v[i]依然可以继续任意选择前i种物品。因为第i种物品是无限的，所以“剩下来的决策空间”仍然是dp[i][j-v[i]]，而不是dp[i-1][j-v[i]]。
也就是说，至少选 1 件的子问题价值是dp[i][j-v[i]] + w[i]。
这两类情况互不重叠、合起来覆盖所有可能性，所以取最大值：
dp[i][j] = max( dp[i-1][j], dp[i][j-v[i]] + w[i] )这个视角特别适合拿去讲给刚接触 DP 的朋友听。展开式消元是“数学推导”，集合划分是“语义解释”，两者配合，就能把方程彻底讲透。
顺便说一句，01 背包为什么是dp[i-1][j-v[i]] + w[i]？因为 01 背包中第i种物品最多只能选一次，“至少选 1 件”强制取出 1 件之后，剩下的容量里就不能再选第i件了，所以剩余部分必须由前i-1种物品来填，依赖的是dp[i-1][j-v[i]]。这是两种背包在方程形式上一个字母之差背后的本质区别。
3. 一维优化：正序循环的真相
3.1 为什么能用滚动数组
很多教科书直接给出空间优化后的代码：
for (int i = 1; i <= n; i++) { for (int j = v[i]; j <= V; j++) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } }第一次看到这个代码的人都会问：为什么能用一个一维数组？为什么内层循环是正序？
答案要从二维方程的结构说起。我们刚推导出的方程是：
dp[i][j] = max( dp[i-1][j], dp[i][j-v[i]] + w[i] )这个方程里只出现了两类数据：
dp[i-1][j]：上一行、同一列的值；dp[i][j-v[i]]：当前行、更小列的值。
滚动数组的本质是把二维数组的“行”压缩成同一个一维数组的不同时刻取值。当我们从i-1行推进到i行时，一维数组dp[j]在更新之前保存的是dp[i-1][j]，更新之后变成dp[i][j]。
所以只要保证：
- 更新
dp[j]时，旧值dp[i-1][j]还在（没被本轮覆盖），供第一项比较； - 更新
dp[j]时，dp[j-v[i]]已经被本轮更新过，也就是它已经携带了“当前第i种物品可能被取过若干件”的信息，供第二项比较。
第 2 点就是正序循环的原因。因为j从小到大递增，更新dp[j]的时候，j - v[i]一定小于j，而更小的列在本轮循环中必然已经被处理过了。这样dp[j - v[i]]拿到的就是dp[i][j-v[i]]，正是我们需要的新值。
3.2 正序与逆序，到底差在哪
为了看清楚正序和逆序的区别，用一个极小的例子手动走一遍。
假设只有一种物品，体积v = 2，价值w = 3，背包容量V = 6。
如果是正序循环：
j = 2：dp[2] = max(0, dp[0] + 3) = 3j = 4：dp[4] = max(0, dp[2] + 3) = 6j = 6：dp[6] = max(0, dp[4] + 3) = 9
注意，dp[4]用到的是dp[2]，而dp[2]已经被本轮循环更新成了3，所以dp[4] = 6表示的其实是“取 2 件该物品”；dp[6] = 9表示取 3 件。一次循环下来，这一件物品被取了 0 件、1 件、2 件、3 件都算进去了，完美符合“无限件”的语义。
如果是逆序循环（01 背包的写法）：
j = 6：dp[6] = max(0, dp[4] + 3)j = 4：dp[4] = max(0, dp[2] + 3)j = 2：dp[2] = max(0, dp[0] + 3)
问题来了：计算dp[6]时，dp[4]还没有被本轮更新，它依然是上一行的值0，所以dp[6] = 3，只相当于取 1 件；计算dp[4]时dp[2]同样还没更新，所以也是 3。最后得到的结果是所有容量下最多只能取 1 件这种物品，这就退化成 01 背包了。
这一个最小例子足以说明问题：完全背包的一维写法必须是正序，因为我们要让dp[j-v[i]]携带“当前物品已经取过”的信息；01 背包的逆序则恰恰是为了避免这一点，保证每个物品只被取一次。
3.3 参考代码：C++ 与 Python
C++ 完整写法：
#include <bits/stdc++.h> using namespace std; const int N = 10005; int v[N], w[N]; int dp[N]; int main() { int n, V; cin >> n >> V; for (int i = 1; i <= n; i++) { cin >> v[i] >> w[i]; } for (int i = 1; i <= n; i++) { for (int j = v[i]; j <= V; j++) { dp[j] = max(dp[j], dp[j - v[i]] + w[i]); } } cout << dp[V] << endl; return 0; }Python 完整写法：
n, V = map(int, input().split()) v = [0] w = [0] for _ in range(n): a, b = map(int, input().split()) v.append(a) w.append(b) dp = [0] * (V + 1) for i in range(1, n + 1): for j in range(v[i], V + 1): dp[j] = max(dp[j], dp[j - v[i]] + w[i]) print(dp[V])这里的dp[V]就是不超过容量V时的最大价值。注意内层循环的下界是v[i]，所以物品体积大于容量的情况天然被跳过，不需要额外判断。
4. 完整算例与手工验证
4.1 算例设计
光看推导还不够，我建议你亲手把一张小 DP 表推一遍。下面这个例子我用了很多年，足够暴露完全背包的所有关键行为。
三种物品：
| 物品 | 体积 v | 价值 w |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
背包容量V = 7。先心算一下最优解：取 2 件物品 1，取 1 件物品 2，总体积是2 + 2 + 3 = 7，总价值是3 + 3 + 4 = 10。这个10就是后面我们要验证的答案。
4.2 逐步构建二维 DP 表
初始化：dp[0][j] = 0，前 0 种物品不管容量多大，价值都是 0。
处理完物品 1（v=2, w=3）之后，dp[1][j]的取值：
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| dp[1][j] | 0 | 0 | 3 | 3 | 6 | 6 | 9 | 9 |
解释一下几个格子：容量 4 可以装 2 件物品 1，价值3*2=6；容量 6 可以装 3 件物品 1，价值9；容量 7 装 3 件物品 1 后还剩 1 个体积装不下，所以还是 9。
处理完物品 2（v=3, w=4）之后，dp[2][j]的取值：
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| dp[2][j] | 0 | 0 | 3 | 4 | 6 | 7 | 9 | 10 |
重点看两个格子：
dp[2][5] = max(dp[1][5], dp[2][2] + 4) = max(6, 3 + 4) = 7，对应 1 件物品 1 + 1 件物品 2，价值 7。dp[2][7] = max(dp[1][7], dp[2][4] + 4) = max(9, 6 + 4) = 10，对应 2 件物品 1 + 1 件物品 2，价值 10。
这里能很清楚地看到dp[2][7]的第二项用到了dp[2][4]，也就是“当前行更小容量”的状态，而不是dp[1][4]。这就是完全背包和 01 背包在计算过程中的关键差异。
再处理物品 3（v=4, w=5），dp[3][j]的取值：
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| dp[3][j] | 0 | 0 | 3 | 4 | 6 | 7 | 9 | 10 |
物品 3 的加入没有改变最终结果，因为它的体积 4、价值 5，单位性价比5/4 = 1.25不如物品 1 的3/2 = 1.5，也不如物品 2 的4/3 ≈ 1.33。最终答案仍然是dp[3][7] = 10。
4.3 用一维过程复现结果
一维数组dp的更新过程可以直观地展示正序循环的威力。
初始：[0, 0, 0, 0, 0, 0, 0, 0]
处理物品 1，v=2, w=3，正序从 2 到 7：
dp[2] = max(0, dp[0]+3) = 3dp[3] = max(0, dp[1]+3) = 3dp[4] = max(0, dp[2]+3) = 6- 依次类推，得到
[0, 0, 3, 3, 6, 6, 9, 9]
处理物品 2，v=3, w=4，正序从 3 到 7：
dp[3] = max(3, dp[0]+4) = 4dp[4] = max(6, dp[1]+4) = 6dp[5] = max(6, dp[2]+4) = 7dp[6] = max(9, dp[3]+4) = 9dp[7] = max(9, dp[4]+4) = 10
得到[0, 0, 3, 4, 6, 7, 9, 10]。
处理物品 3，v=4, w=5，正序从 4 到 7：
dp[4] = max(6, dp[0]+5) = 6dp[5] = max(7, dp[1]+5) = 7dp[6] = max(9, dp[2]+5) = 9dp[7] = max(10, dp[3]+5) = 10
最终仍然是[0, 0, 3, 4, 6, 7, 9, 10]，dp[7] = 10。
我建议你在纸上照着这个表推一遍，推完你就能彻底理解“当前行状态被后续容量复用”是怎么回事。很多读者反馈说看完这段手动过程，再看代码就顺了，因为代码里每一次dp[j] = max(dp[j], dp[j-v[i]] + w[i])背后对应的就是这张表上的一个格子。
5. 经典变形与工程落地细节
5.1 恰好装满的初始化陷阱
完全背包题经常问“恰好装满背包的最大价值”，而不是“不超过容量”。
这两种问法的代码几乎一样，差异只在初始值。
- 问“不超过容量”：
dp[j]全部初始化为0，因为容量没用满也是合法状态，任意容量都可以由“什么都不装”这个方案打底。 - 问“恰好装满”：
dp[0] = 0，dp[1..V]初始化为一个极小负数，比如-0x3f3f3f3f。原因是“恰好装满”要求每个容量都必须由物品精确拼出来，只有容量 0 是天然的合法起点，其他容量在没有物品时都是非法的，用极小值-INF表示“不可达”。这样在max运算里，非法状态自然会被排除。
举个例子：只有一种物品，体积 2、价值 3，容量 7。
- 不超过容量：答案
9，装 3 件物品 1，剩 1 体积无所谓。 - 恰好装满：容量 7 无法由若干个 2 拼出来，答案是
-INF，表示无解。
但如果容量是 6，恰好装满的答案就是9，因为 3 个 2 正好凑满 6。
初始化这个坑非常隐蔽。很多人写的思路没问题，代码也没写错，就是初始值用错了，结果整题答案偏了一大截，这种题在 LeetCode 的零钱兑换系列里非常典型。
5.2 求方案数与最小件数
完全背包不止能求最大价值，两个常见的变体是方案数和最小件数，它们的状态转移都是从同一个框架衍生出来的。
求方案数：dp[j]表示容量j被完全装满的方案总数。
for (int i = 1; i <= n; i++) { for (int j = v[i]; j <= V; j++) { dp[j] += dp[j - v[i]]; } }初始dp[0] = 1，其余为 0。因为“容量 0 装满”只有空集一种方案。内层同样是正序，表示同一物品可以反复取。
举一个经典例子：硬币面额[1, 2, 5]，目标金额 5。方案有 4 种：1+1+1+1+1、1+1+1+2、1+2+2、5。按方程手动推一下，最终dp[5] = 4，正确。
求最小件数：dp[j]表示装满容量j所需的最少物品件数。
for (int i = 1; i <= n; i++) { for (int j = v[i]; j <= V; j++) { dp[j] = min(dp[j], dp[j - v[i]] + 1); } }初始dp[0] = 0，其余为INF。这个写法其实就是“零钱兑换”的经典解法：给定硬币面额和目标金额，求最少硬币数来凑出目标金额。
这两个变形再次体现了完全背包 DP 框架的通用性：只要把方程里的max换成min或sum，再调整好初始值，同一个遍历顺序可以解决一大类“无限物品组合”问题。
5.3 什么时候不能用完全背包正序
正序遍历不是万能的。多重背包就是典型的反例：每种物品有有限件数c[i]，既不是 01 背包的 1 件，也不是完全背包的无限件。如果直接把多重背包当成完全背包做正序循环，同一物品会被取超过c[i]次，答案必然偏大。
多重背包的常规解法是把第i种物品的c[i]件拆分成若干组，每组按二进制系数打包成新的物品，然后跑 01 背包。还有更高阶的单调队列优化，复杂度能降到O(N*V)，但那就是另一个话题了。
另外要记住：完全背包正序的前提是“物品可以无限取”。一旦题目加了限制条件，比如“每个物品最多用 3 次”“每个物品必须至少选一次”“物品之间有互斥关系”，正序裸循环就不能直接用了，需要回到状态定义重新推导。
6. 常见问题与排错实录
6.1 “我写的完全背包答案偏小，怎么查？”
这是最常遇到的报错场景。代码看上去没问题，但答案总比预期小。优先检查两件事：
- 内层循环是不是写成了逆序
for (int j = V; j >= v[i]; j--)。如果写成逆序，代码其实退化成了 01 背包，完全背包的“无限件”特性就没了。检测方法很简单：构造一个单物品数据，体积 2、价值 3、容量 6，正确输出应该是 9（3 件物品 1）。如果输出是 3，那就是逆序了。 - 初始值是不是用错了。题目要求“恰好装满”却把所有
dp初始化为 0，或者反过来，都会导致答案系统性偏差。
6.2 “正序循环会不会导致某件物品被用得太多了？”
这是一个特别好的问题。有人担心正序会让每轮循环都无限叠加同一件物品，最后把容量全部塞满一件物品，导致漏掉其他组合。
这种担心其实是多余的。因为dp[j] = max(dp[j], dp[j-v[i]] + w[i])里，每一轮外层物品循环都会保留dp[j]旧值和放入当前物品的新值之间的最大值。正序确实允许同一件物品被多次取，但最终取多少件是由max决定的：如果取 3 件不如取 1 件物品 A + 2 件物品 B 的价值高，max就会选择后者。换句话说，正序只是“允许”无限件，并不会“强迫”无限件。真正决定方案的还是价值最大化这个目标。
01 背包里逆序之所以必要，是因为它必须“禁止”同轮复用；完全背包正序之所以可行，是因为它必须“允许”同轮复用。两者都是状态依赖关系在代码层面的真实映射，而不是机械的背诵要点。
6.3 一道题区分三种背包
最后分享一个我常用的自测题，能在五分钟内确认你是否真的理解了三种背包的差异。
有一个容量为 10 的背包，只有 1 种物品，体积 3、价值 5。
- 01 背包：最多取 1 件，答案 5。
- 完全背包：最多取 3 件（
3*3=9，取 4 件超容量），答案 15。 - 多重背包，限制最多取 2 件：答案 10。
用同样的输入，分别用三种写法的代码跑一遍，看输出是不是5、15、10。如果哪一个对不上，问题几乎一定出在内层循环方向或者状态依赖上。
我踩坑无数之后的体会是：完全背包的状态转移方程其实不是靠背的，它是从一个很自然的“枚举 k 件”的朴素思路，通过展开式观察消元推出来的。动手推一遍展开式，比看十遍代码都有用。你现在如果能独立把dp[i][j] = max(dp[i-1][j], dp[i][j-v[i]] + w[i])从枚举式推导出来，再亲手画一张小容量 DP 表验证，那你对这个知识点的掌握就已经超过绝大多数人了。
