完全背包与01背包的区别：状态转移方程、遍历顺序及经典例题详解

1. 从一道“可以重复拿”的题目说起：先搞懂完全背包和01背包差在哪

在讲完全背包之前，我默认你已经接触过01背包。如果还没看过，建议先找一篇01背包的入门文章把状态定义搞明白，因为完全背包就是在01背包的框架上改了“一个条件”，但就是这一个条件，把很多人的思路带偏了。

我当年第一次做完全背包的时候，心里想的是：既然物品可以无限拿，那我是不是要把每种物品复制成好多个，然后当成01背包来做？比如容量是10，某件物品重量是3，那我就复制3份或者4份，然后再跑一遍01背包。这个思路不能说全错，但属于“明明有电梯不走，偏要爬楼梯”——能到，但特别累，而且稍不注意就会复制出问题。

先看题目原型。假设有一个背包，容量为C，现在有N种物品，每种物品的重量是w[i]，价值是v[i]，每种物品的数量是无限的。问：在不超过背包容量的前提下，能装下的最大总价值是多少？

注意关键词：无限。这就是完全背包和01背包最本质的区别。01背包里，每个物品你只有“拿”和“不拿”两个选择，拿了就没了；完全背包里，每个物品你可以拿0次、1次、2次……一直拿到放不下为止。

这个区别直接导致状态转移方程的变化。01背包的状态转移是：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

这里dp[i-1][j-w[i]]表示我在“前 i-1 个物品里做决定”的基础上，再决定拿第 i 个物品。因为第 i 个物品只能拿一次，所以拿到它之后，前面只能是 i-1 个物品的决策结果。

完全背包不一样，我在决定要不要拿第 i 个物品的时候，如果选择拿，拿完之后我还是可以在前 i 个物品里继续做决定——因为我还可以再拿一次。所以状态转移变成：

dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

注意，第二项从dp[i-1][j-w[i]]变成了dp[i][j-w[i]]。这个i和i-1的差别，就是“能不能重复拿”的数学表达。

去年我在公司带一个实习生，他看完这两行方程之后问我：“老师，这不就差一个下标吗？有这么重要吗？”我说你别小看这个下标，你把它写成一维数组跑一遍，就知道差别有多大了。后面我会专门讲这个。

另外还要提一下，在日常的算法题和面试里，完全背包最常见的两种考察形式是“最大价值问题”和“方案数问题”。最大价值就是上面说的那个模型，方案数问题则是问“有多少种凑法”，比如经典的“零钱兑换II”。方案数问题的转移方程只需要把max换成+，但初始化的方式会有一点变化，后面我也会提到。

接下来我把完全背包的完整解法拆成几步，从二维dp开始讲，讲完再优化成一维dp，最后给几个常见变体和面试高频坑点。保证你看完能直接AC掉LeetCode上那几道经典题。

2. 二维dp实现：先把最朴素的思路写对

2.1 状态定义和初始化

先说状态定义。我们用dp[i][j]表示：在前 i 种物品中任意选取（每种物品可以选任意次），放入容量为 j 的背包，能获得的最大价值。

这里一定要把“前 i 种物品”和“容量为 j”这两个维度理解透。前者是物品的维度，后者是容量的维度。二维数组的两根轴，一根管物品范围，一根管背包容量，缺一不可。

初始化的时候，dp[0][j]表示“在前0种物品里选”，那任何容量下都选不出东西，价值就是0。dp[i][0]表示“容量为0”，那也什么都放不下，价值也是0。所以整个二维数组初始化成全0就行，不用额外处理边界。

不过有一种情况需要特殊注意：如果题目让你求的是“恰好装满背包”时的最大价值，那初始化就不一样了。要把dp[0][0]设为0，把dp[0][j]（j>0）设为负无穷（一般用-INF），表示“容量没装满”这个状态是不可达的。这个细节很容易被忽略，但真遇到了就是致命的。

2.2 三层循环的朴素写法：最直白但最慢的版本

理解了状态定义之后，最直观的写法反而不一定是两层循环，而是三层循环——对每种物品，枚举拿几个。

伪代码如下：

// N是物品数量，C是背包容量 // w[i]是第i种物品的重量，v[i]是第i种物品的价值 // 物品编号从1开始 for (int i = 1; i <= N; i++) { for (int j = 0; j <= C; j++) { for (int k = 0; k * w[i] <= j; k++) { dp[i][j] = max(dp[i][j], dp[i-1][j - k*w[i]] + k*v[i]); } } }

这个写法用了一个额外的k循环，表示第i种物品拿k件。逻辑非常直白：不拿就是k=0，拿1件就是k=1，拿2件就是k=2……把所有可能都枚举一遍，取最大值。

但这样做的复杂度是 O(N * C * (C/w[i]))，最坏情况下接近 O(N * C^2)，数据量一大就挂了。比如背包容量是1000，物品有100种，最坏情况下的计算量就是亿级，在LeetCode上大概率超时。

所以三层循环这个版本，我建议你只是用来验证小数据，或者帮助自己理解“为什么完全背包是多阶段决策问题”。真正写题的时候，要么用后面的二维优化写法，要么直接用一维写法。

2.3 去掉k循环的二维优化写法：一个观察改变复杂度

接下来要说的这个优化，是理解完全背包的关键一步，也是面试中经常被追问“为什么能这么优化”的点。

仔细观察上面那个三层循环，对固定的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][j-w[i]]的值，会怎样？dp[i][j-w[i]]算的是：

max(dp[i-1][j-w[i]], dp[i-1][j-2*w[i]] + v[i], dp[i-1][j-3*w[i]] + 2*v[i], ...)

发现没有？dp[i][j-w[i]] + v[i]恰好等于：

max(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], ...)

这正好就是dp[i][j]中除了第一项dp[i-1][j]之外的所有候选值的最大值。

于是退化到：

dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

就这么一个简单的数学观察，把原来的三层循环降成了两层循环，复杂度从 O(NC^2) 降到 O(NC)，是质的飞跃。

我举个例子帮助理解。假设当前物品重量w=3，价值v=5，背包容量j=9。用三层循环的话，你要枚举k=0,1,2,3四种情况，分别算价值0、5、10、15，然后取最大值15。但是如果你已经知道了容量为6（也就是j-w=9-3=6）时的最优解是10（这个10可能来自拿了两件当前物品，也可能来自前面的物品组合），那你直接用10+5=15，就能拿到“拿一件当前物品之后继续在3容量里找最优”的结果。这比一个个试快多了。

二维优化的完整代码：

for (int i = 1; i <= N; i++) { for (int j = 0; j <= C; j++) { if (j >= w[i]) { dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]); } else { dp[i][j] = dp[i-1][j]; } } }

答案是dp[N][C]。

这个二维版本的空间复杂度是 O(N*C)，比三层循环版写起来简洁，思路也比较清楚。面试的时候如果你能把上面那段“观察”讲给面试官听，基本能证明你是真的懂DP，不是背模板。

3. 一维优化：为什么完全背包要正着遍历容量

3.1 从滚动数组到一维dp：空间复杂度降维打击

二维dp的空间复杂度是 O(N*C)，当 N 和 C 都很大时，内存可能会爆。比如 N=5000，C=5000，那就是2500万个int，约100MB，多数在线判题系统会直接报MLE。

于是我们需要空间优化。思路是这样的：观察状态转移方程dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])，发现dp[i][j]只依赖两个东西：上一行的dp[i-1][j]，以及本行的dp[i][j-w[i]]。

如果我们在内层循环正着遍历j从 0 到 C，那么在计算dp[j]的时候，dp[j-w[i]]已经是本轮的更新结果了——这正是我们需要的dp[i][j-w[i]]。而dp[j]在被覆盖之前，存的还是上一轮的dp[i-1][j]——这正好是方程里的另一项。

所以一维写法非常简洁：

for (int i = 1; i <= N; i++) { for (int j = w[i]; j <= C; j++) { dp[j] = max(dp[j], dp[j-w[i]] + v[i]); } }

注意，内层循环是j从w[i]到C正着走。这个“正着走”就是完全背包和01背包在代码层面的分水岭。

01背包一维写法是倒着走：

for (int i = 1; i <= N; i++) { for (int j = C; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j-w[i]] + v[i]); } }

为什么01背包要倒着走？因为dp[j-w[i]]必须是上一轮的结果，不能是这一轮已经更新过的。如果正着走，j从小到大递增，dp[j-w[i]]很可能已经在当前物品的迭代中被更新过了，这就等于“同一个物品被拿了多次”，正好和01背包不允许重复拿的要求冲突。

但完全背包恰恰需要“同一个物品可以被多次拿”，所以正着走刚刚好。

这个对应关系，我建议你反复咀嚼几遍。之前有读者问我：“老师，如果我记反了，比如完全背包写成倒序，会怎样？”答案是：结果会变成“每种物品最多只能拿一次”，也就是退化成01背包的结果了。如果你在做的是“零钱兑换”这类题目，那答案就会错得离谱。

还有一个坑，初始化dp数组时，如果求的是“恰好装满”的最大价值，dp[0]应该设成0，其他设成-INF。但如果求的是“不超过容量”的最大价值，那全部初始化成0就行。两种初始化带来的结果差异，在实际题目中非常容易踩雷。

3.2 正序和逆序的直观理解：用生活场景拆解一下

很多教程会直接告诉你“01倒序，完全正序”，但不解释为什么。我换一个生活化的说法来解释。

你可以把01背包想象成“超市限购”：每种商品每人只能买一件。你在货架前从左往右逛（这就像正序遍历），如果看到一件商品便宜，你放进购物车了，再逛到更便宜的同款商品（其实不存在，因为限购），你不会重复拿。

但完全背包像是“不限量自助餐”：每道菜你可以反复去拿。你从左往右走，看到一个好吃的，拿了一份；走了两步，觉得还能再吃，回头又拿了一份。正序遍历恰好模拟了这种“拿了之后还可以再回来拿”的机制。

反过来，如果你倒着走（从右往左），每道菜你只看了一眼，拿不拿就决定了，不会回头，这就是01背包。

这个类比不算特别精确，但对于刚开始接触DP的人来说，能帮助建立直觉。等你写多了，自然会理解到“正序和逆序的差别，本质上是对状态依赖关系的控制”。

3.3 对比表格：01背包 vs 完全背包

我把两者的关键区别整理成一个表格，方便你在复习的时候一眼扫过去：

如果你能把上面这张表完全理解，而不是靠死记硬背，那完全背包这块就过了大半关了。

4. 经典例题实战：拿LeetCode 322和518练手

4.1 零钱兑换（LeetCode 322）：求最小硬币数量

题目是这样的：给定不同面额的硬币和一个总金额，写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。每种硬币的数量是无限的。

这是一道非常标准的完全背包“最小价值”变体。为什么是最小价值？因为它求的不是“最大总价值”，而是“最少硬币数”。

思路如下：定义dp[j]表示凑成金额j所需的最少硬币数。初始化的时候dp[0] = 0，其他dp[j]设为一个很大的数，比如INT_MAX或者amount + 1。这里用amount + 1有个好处——如果一个值永远是amount + 1，就说明这个金额凑不出来，最后返回 -1 即可。

状态转移：

dp[j] = min(dp[j], dp[j - coin] + 1)

注意这里是min，因为我们要最少的硬币数。核心代码：

int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, amount + 1); dp[0] = 0; for (int coin : coins) { for (int j = coin; j <= amount; j++) { dp[j] = min(dp[j], dp[j - coin] + 1); } } return dp[amount] > amount ? -1 : dp[amount]; }

这里有几个点需要确认一下：

第一，dp[j]定义为“凑成金额j的最少硬币数”，边界是dp[0]=0，表示凑0元需要0个硬币。

第二，内层循环从coin开始，正序遍历，因为硬币无限。

第三，返回的时候判断dp[amount] > amount而不是dp[amount] == INT_MAX，是为了防止整数溢出。如果初始化用amount + 1，这个判断就特别安全。

我之前有个学员特别喜欢把初始化的值设成INT_MAX，然后转移的时候写dp[j] = min(dp[j], dp[j - coin] + 1)。如果dp[j-coin]是INT_MAX，加1就溢出了，变成负数，直接污染结果。这就是为什么我建议用amount + 1作为哨兵值。

4.2 零钱兑换II（LeetCode 518）：求凑成总金额的方案数

这个题目和322非常像，但问题从“最少需要几个硬币”变成了“一共有多少种凑法”。本质上是完全背包的“方案数”变体。

状态定义：dp[j]表示凑成金额j的方案总数。初始化dp[0] = 1，表示凑0元只有一种方案（什么都不拿）。其他dp[j]初始化为0。

状态转移：

dp[j] = dp[j] + dp[j - coin]

这是在枚举每个硬币面额时，把“不使用当前硬币”的方案数（原来的dp[j]）和“使用当前硬币”的方案数（dp[j - coin]）加起来。

核心代码：

int change(int amount, vector<int>& coins) { vector<int> dp(amount + 1, 0); dp[0] = 1; for (int coin : coins) { for (int j = coin; j <= amount; j++) { dp[j] += dp[j - coin]; } } return dp[amount]; }

这个代码有一个非常隐蔽的坑，就是外层循环务必是硬币，内层循环务必是金额。如果你把内外层交换了，得到的结果会变成“排列数”而不是“组合数”。

举个例子你就明白了。假设硬币面额是 [1, 2]，总额是 3。组合数的话，只有两种凑法：1+1+1 和 1+2。但你如果把内层循环换成硬币，外层是金额，那相当于你要依次算“金额为1的所有硬币组合”“金额为2的所有硬币组合”……这样1+2和2+1会被当成两种不同的方案，结果就是3。这正是很多人写这道题WA（Wrong Answer）的原因。

顺便提一句，如果题目要求“排列数”（比如爬楼梯问题，把不同顺序算作不同方案），那就该把外层循环改成金额，内层循环改成物品。这个细节对理解DP的“顺序敏感性”非常有帮助，值得好好体会。

4.3 完全平方数（LeetCode 279）：不太像背包的背包题

很多人的第一反应是“这题跟背包有什么关系”？但它还真是完全背包，只是换了个皮。

题目：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n，你需要让组成和的完全平方数的个数最少。

在这个题里，“物品”就是每个完全平方数i*i，“背包容量”就是n，“价值”就是1（每选一个平方数，个数加1）。因为每个平方数可以重复选，所以是完全背包。

核心代码：

int numSquares(int n) { vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i * i <= n; i++) { int square = i * i; for (int j = square; j <= n; j++) { dp[j] = min(dp[j], dp[j - square] + 1); } } return dp[n]; }

这个题用完全背包的思路做，时间复杂度 O(n * sqrt(n))，完全够用。而且它比零钱兑换更简单一点，因为物品序列是固定的（从1到sqrt(n)的平方数），根本不用自己去想有哪些物品。

我为什么把这个题也列出来？因为它很典型地展示了DP建模的思维方式：把看似不是背包的题目转化为背包模型。面试的时候，如果你能一眼识别出这种“披着羊皮的狼”，会非常加分。

5. 变体与延伸：除了最大价值和方案数，还有哪些考法

5.1 完全背包求具体方案：从“求值”到“求路径”

前面讲的都是求最优值或方案数，但有些题目会问你“把哪些物品放进了背包”。这种题属于“输出具体方案”的问题。

一般的做法是：先用DP算出最优值，然后反向回溯。你从dp[N][C]开始，如果dp[i][j] == dp[i-1][j]，说明第 i 种物品没拿；如果dp[i][j] == dp[i][j-w[i]] + v[i]，说明第 i 种物品拿了，然后继续看dp[i][j-w[i]]。

注意，因为完全背包允许拿多次，所以回溯的时候不是直接跳到i-1，而是可能还要留在i这一行继续回溯。这个逻辑跟01背包略有区别。如果你用一维dp做完了，想回溯方案，就有点麻烦了——一维数组把“路径信息”丢了，所以建议输出方案时用二维dp。

5.2 多重背包与完全背包的边界：一种物品最多拿k次怎么办

这里顺带提一下多重背包，因为初学者很容易把完全背包和多重背包搞混。多重背包是每种物品有一个数量上限k[i]，不能无限拿。

求解多重背包的朴素做法是把每种物品拆成k[i]个独立的01背包物品，复杂度较高。更优的做法是利用二进制拆分，把k[i]拆成1, 2, 4, ..., 2^m, rest几个部分，每个部分当作一个01背包物品。这个技巧在竞赛中很常见，但面试里考察频率不如完全背包高。

如果面试官问你“能不能把多重背包转成完全背包”，你直接说“不能，因为数量上限限制了重复拿取次数，这和完全背包的无限次有本质区别”，就足够展示你对这个知识点的理解深度了。

5.3 完全背包的适用场景：从算法题到实际工程

虽然我们讨论的是算法题，但完全背包的思想在实际工程中也有不少应用场景。

举几个例子：

• 预算分配：假设你有一个总预算，有多个项目，每个项目可以投入任意金额（对应无限次选择），求收益最大化的投入方案。这就是一个标准的完全背包问题。

• 资源调度：在云计算中，资源池里有多种规格的虚拟机，每种规格可以按需启动，目标是在满足总资源需求的前提下最小化成本——这个建模思路和完全背包高度相似。

• 切割问题：有一根长度为 L 的钢管，可以按不同长度切割出售，每种长度的价格不同，不限切割次数，问最大收益。这是一个非常经典的完全背包变体，长度就是物品重量，价格就是价值，钢管总长就是背包容量。

我在实际工作中遇到过类似的场景，虽然是业务需求而不是算法竞赛题，但底层的DP建模逻辑完全一致。这也说明，掌握DP不是单纯为了刷题，它对培养“把现象问题抽象成数学模型”的能力帮助很大。

6. 常见问题与排查技巧：这些坑我全都踩过

6.1 遍历顺序写反了：正序写成逆序，逆序写成正序

这是完全背包里最常见的错误。症状是：小数据测试用例能过，但大数据WA。

检查方法很简单：你拿一个只有一件物品、重量为1、价值为2、背包容量为5的例子，跑一遍代码。如果答案是10，说明正序写对了；如果答案是2，那很可能是写成逆序了，退化成了01背包。

我的习惯是在写完DP循环后，先用笔在纸上模拟一遍只有一件物品的情况，确认结果符合“无限次取”的预期，再去跑大用例。这个小习惯帮我省了很多debug时间。

6.2 状态定义不清晰导致初始化错误

很多人在做“恰好装满”类题目时，初始化还是全0，结果答案比预期小或者出现奇怪的数字。

“恰好装满”的初始化规则我再说一遍：dp[0] = 0，其余的设为-INF（求最大值）或者+INF（求最小值）。只有这样才能保证“从容量0逐步装满”这个状态是合法路径，其他未装满的状态都是非法路径。

如果你是用一维dp，注意初始化向量的时候要显式指定填充值，不要默认用0。C++的话就是vector<int> dp(C+1, -1e9)，Java就是int[] dp = new int[C+1];然后循环填充-INF，Python就是dp = [float('-inf')] * (C+1)。

6.3 下标越界和物品顺序问题

有些人在写内层循环时，直接从j = 0开始遍历，然后在转移方程里加一个if (j >= w[i])判断。这样做是对的，但要注意：如果不加判断就直接访问dp[j-w[i]]，当j < w[i]时下标为负，直接越界。

另外，在“组合数”问题中，物品顺序不能颠倒。我说的是两层循环的嵌套顺序——外层必须是物品，内层必须是容量。你要是写反了，就会把组合数算成排列数。这个问题在“零钱兑换II”里特别容易出现，代码看起来一模一样，就是两层循环换了个位置，结果天差地别。

6.4 用int溢出导致结果错误

在方案数类问题中，如果题目说“结果可能很大，请对 10^9 + 7 取模”，那你在转移方程里就要每一步都取模。如果忘了取模，或者在最后才取模，中间就已经溢出，答案直接错。

在求最小值的题目里，用INT_MAX做哨兵值时，转移方程里千万别直接dp[j-coin] + 1，因为INT_MAX + 1会变成负数，反而比dp[j]小，导致 min 结果全是负数。这是我反复强调的一点，也是很多人在LeetCode 322上卡住的原因之一。

以下是FAQ速查表，我自己在复习时会过一遍：

6.5 动态规划题目通用的自测方法

最后分享一个通用的自测方法：写DP题，一定要先写小规模暴力解，再用DP解去对拍。

我刷题早期吃过很多亏，觉得自己DP思路没问题，然后一提交就WA。后来学乖了，简单题还好，难题我先写一个递归暴力版本（哪怕会超时），保证它在小数据上是对的。然后拿DP的结果和暴力解在小数据上逐一比对，一旦不一致，马上就能定位是状态定义错了还是转移方程错了。

这个方法对完全背包尤其有用，因为三层循环的朴素版本在小数据上能跑，正好可以作为参考答案。等你把二维优化和一维优化写好之后，用同样的随机数据去对拍，基本一盯一个准。

7. 一点个人的做题体会

完全背包这个知识点，如果你只是为了应付面试，把“完全背包正序、01背包逆序”记住就行。但我个人建议还是花点时间把转移方程为什么从dp[i-1]变成dp[i]琢磨清楚。

因为动态规划的东西，你靠记忆是背不完的——变体太多了，今天是最大价值，明天是最小数量，后天是方案数，大后天还可能叠加“恰好装满”“顺序敏感”等边界条件。只有把状态定义、转移来源、遍历顺序这三件事理解透，碰到任何变体，你都能自己推导出来。

最后再送一个小技巧：刷DP题的时候，别只盯着AC，试着用“手推状态转移表”的方式把每一步在纸上画一遍。比如完全背包，拿两个物品、容量大概是6，把dp数组从头到尾填一遍。这个过程看起来慢，但真的能帮你建立肌肉记忆。我当年就是这么把DP的基础打牢的，后来遇到很多复杂的背包变体，基本都能举一反三。