背包问题与动态规划：从0/1背包到状态转移方程的深度解析

背包问题在动态规划里基本算是“门面”。不只是算法竞赛，我见过不少工程岗面试、甚至一些偏底层的业务场景，都会拿背包问题的变体来考察候选人的建模能力。原因很简单：它看起来是一个具体问题，但抽象之后几乎覆盖了动态规划最核心的建模方法——状态定义、转移方程、空间优化、枚举顺序取舍，全都在一个几十行的代码里体现出来。

如果你刚开始接触动态规划，背包问题可能是最值得花时间去啃的模型。它不会像区间DP那样对思考技巧要求极高，也不会像状态压缩DP那样需要位运算基础，但它能帮你建立一套通用的思考框架。等你把0/1背包、完全背包、多重背包之间的差异吃透，再去看其他动态规划题，状态设计那一步会顺很多。

这篇文章我会从最基础的0/1背包讲起，把状态定义、转移方程的由来讲明白，再做一维空间优化，然后扩展到完全背包、多重背包以及几个高频变体。每一部分都会解释清楚“为什么这么写”，尤其是遍历顺序和初始化这两块，因为过度依赖模板往往会在这里踩坑。

1. 背包问题的本质与动态规划为什么适合它

1.1 背包问题到底在解决什么

我先从一个最朴素的问题描述开始：有一个容量为W的背包，n件物品，每件物品有重量w[i]和价值v[i]，要求选出若干件装入背包，使总重量不超过W，同时总价值最大。

这个描述听起来很简单，但难点在于：每件物品都有“选”和“不选”两种状态，n件物品的组合方式是2^n种。如果你真的去枚举所有组合，当n等于50时就已经是不可接受的计算量了。也正因为这个组合爆炸的性质，背包问题不能靠搜索或简单贪心去解决。

这里值得多说一句：很多人会先尝试贪心，就是按“性价比”（价值/重量）从高到低选。这个思路在某些特定条件下成立，比如物品可以分割时，但在0/1背包里贪心是错的。因为物品不可分割，贪心选性价比高的物品可能导致背包剩余空间没被充分利用，而放弃一个低性价比但能恰好填满剩余空间的物品。动态规划之所以适用，是因为它可以同时考虑“容量占用”和“价值积累”这两个维度，把全局最优解拆解成一系列子问题的最优解。

1.2 为什么状态设计是“前i件物品 + 容量j”

背包问题最关键的一步，是定义dp数组的含义。我第一次学的时候也觉得这个定义有点“凭空冒出来”，但其实它是从决策过程倒推出来的。

你在处理第i件物品时，面临的决策是：放进去，还是不放。这个决策只依赖两个信息：当前已经考虑了哪些物品（前i件），以及当前剩余容量是多少（这里用j表示当前背包容量的上限）。因此，状态可以定义成：

dp[i][j]：考虑前i件物品，在背包容量不超过j的前提下，能获得的最大价值。

为什么这个定义可行？因为无论前i-1件物品怎么选，它的结果都可以用一个“在容量为某种情况下能达到的最大价值”来表示，而这个结果与第i件物品无关。当我们决定是否放入第i件物品时，只需要基于前i-1件物品的子问题结果，去比较“不放”和“放进去”哪个价值更大。

这种“将一个大问题分解为若干个子问题，且子问题之间可以通过状态递推”的结构，正是动态规划能高效解决背包问题的根本原因。它不是靠剪枝，而是靠状态的合并——把2^n种组合压缩成n*W个状态。

1.3 状态转移方程的推演思路

状态定义清楚了，转移方程就是顺着“选与不选”的思路写下来。

对于第i件物品（注意下标从1开始计数，方便和dp数组对应），容量为j时：

• 如果背包容量连第i件物品都放不下，也就是j < w[i]，那只有一个选择：不放。此时dp[i][j] = dp[i-1][j]。
• 如果容量允许放入，那就在“不放”和“放”两种方案里取最大值。“不放”对应dp[i-1][j]；“放”则意味着前i-1件物品只能占用j - w[i]的容量，所以价值是dp[i-1][j - w[i]] + v[i]。

写成公式就是：

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

这个式子看起来简单，但它包含了一个非常重要的思想：dp[i][j]不关心前i-1件物品具体选了哪些，它只关心在特定容量下能达到的最大价值。这就是最优子结构的一个典型体现。很多初学者会把注意力集中在代码上，其实深入理解这个方程“为什么可以这样合并状态”，才是真正理解动态规划的开始。

2. 动态规划的三板斧：状态、转移、初始化

2.1 状态定义与数组尺寸选择

上一节已经给出了状态定义。在实际写代码前，还需要确定dp数组的尺寸：如果n件物品，背包容量为W，那么dp数组通常是(n+1)行、(W+1)列。行数多出来的1是为了处理“前0件物品”这个边界状态，列数多出来的1是为了表示容量从0到W的所有可能性。

我从这里补充一个细节：如果把容量直接定义为“不超过j”，那么dp[0][j]的初始值就是0，因为前0件物品无论如何都不能产生价值。但如果你遇到“恰好装满背包”这类变体，初始化就会完全不同。这是很多细节题的一个分水岭，我会在后面专门用一个小节展开讨论。

另一个容易被忽略的问题是数组的物理含义：dp[i][j]只是“考虑了前i件物品”，并不代表第i件物品已经被选中。它是一个决策过程的状态快照，而不是“选了哪些物品”的记录。理解这一点，后续做求具体方案、回溯选法时就不会被绕晕。

2.2 两层循环的枚举顺序

实现背包问题时，常规做法是外层循环枚举物品，内层循环枚举容量。外层物品的枚举顺序就是“一件一件处理物品”的自然过程，内层容量可以正向也可以反向，具体要看是一维还是二维。二维版本正反都行，因为dp[i][j]依赖的是dp[i-1][...]，不会在同一轮被覆盖。

这里我额外说明一下外层为什么必须放在物品层：因为状态dp[i][j]依赖的是前i-1件的结果。如果你先枚举容量、再枚举物品，那么在第j个容量状态下，你无法保证dp[i-1][j-w[i]]已经被计算完成。说得更直白一点，内层循环对同一个容量j遍历所有物品时，物品之间存在交叉依赖，就会破坏动态规划的递推顺序。

落实到伪代码：

• 外层循环：for i in range(1, n+1)
• 内层循环：for j in range(W+1)

内层循环内的判断结构通常是：

if j < w[i-1]: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1])

这个模板非常固定，但是背后是完整的决策树。我把这段代码写出来，是因为很多初学者会在这里少写一个else分支，导致容量不足时dp[i][j]被错误地赋成默认值0，而不是继承上一行的结果。这个小错误在数据量小时看不出来，但一旦出现“容量不够却仍然拿默认值比较”的情况，结果就会偏大。

2.3 初始化的两个常见流派

初始化直接决定dp的语义，也就是状态是在“不超过容量”还是“恰好装满”的前提下求解。两者对应的初始化方式完全不同。

• “不超过容量”求最大值：dp[0][j] = 0。也就是说，前0件物品在任意容量下，最大价值都是0，因为没有物品可选。
• “恰好装满”求最大值：dp[0][0] = 0，dp[0][j>0] = 负无穷。因为前0件物品不可能恰好装满一个非零容量，用负无穷来表示“这个状态不可达”。

这是一个很容易被忽视但非常关键的细节。很多LeetCode风格或实战场景中的背包题，并不会直接写“不超过容量”，而是要求“恰好用完”或者“每个位置都由物品填充到正好”，这时如果你还填0，得到的结果会比预期偏大，而且很难排查。

2.4 为什么状态转移要关注“依赖的上一行”

二维版本的规律很明显：dp[i][j]在更新时，只用到了dp[i-1][j]和dp[i-1][j-w[i]]。这意味着当前行的计算只依赖上一行，与更早的行无关。这个性质为空间优化提供了理论基础。如果只是想先让代码跑对，二维版本完全够用；但如果追求内存占用更低、或者面对W和n很大的场景，就必须做滚动数组或一维化。

我在实际做题和写业务模型时，很少会在生产环境里直接开一个n*W的二维数组，尤其当W达到几十万时。学习阶段二维数组有助于理解，但真正使用还是要掌握一维优化。

3. 0/1背包的进阶：滚动数组与一维优化

3.1 从二维到一维：滚动数组的演进

既然dp[i][j]只依赖dp[i-1][j]和dp[i-1][j-w[i]]，那么理论上只需要保留上一行的结果就够了。最常见的优化方式是使用一维数组dp[j]表示“当前物品处理完后，容量为j时的最大价值”。

但这里有一个必须想清楚的问题：一维数组在更新过程中会被覆盖，如果覆盖顺序不对，就会导致同一件物品被重复使用，状态就错了。

我先给出正确代码，再解释为什么要倒序：

def knapsack_01_1d(weights, values, W): dp = [0] * (W + 1) n = len(weights) for i in range(n): for j in range(W, weights[i] - 1, -1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[W]

这里的核心是内层循环从W向下遍历到w[i]。如果改成从w[i]正向遍历到W，同一个物品会被重复选择。

3.2 为什么倒序遍历能防止物品被重复选取

我用一个很小的例子来说明。假设只有一个物品，重量为2，价值为3，背包容量W为4。

• 初始化dp = [0, 0, 0, 0, 0]
• 如果正序遍历j从2到4：
  • j=2：dp[2] = max(dp[2], dp[0]+3) = 3
  • j=3：dp[3] = max(dp[3], dp[1]+3) = 3
  • j=4：dp[4] = max(dp[4], dp[2]+3) = max(0, 3+3) = 6

看到问题了吗？在j=4时，dp[2]已经被这一轮更新成3，于是这个3被当作“已经取过该物品后的状态”再次加上3，等于同一件物品被取了两遍，总价值变成6。这明显是错误的。

如果是倒序遍历：

• j=4：dp[4] = max(dp[4], dp[2]+3) = 3，此时dp[2]还是上一轮的0
• j=3：dp[3] = max(dp[3], dp[1]+3) = 3
• j=2：dp[2] = max(dp[2], dp[0]+3) = 3

最后dp[4] = 3，结果正确。

生活化的类比是：正序遍历就像你在同一个货架上反复取同一件商品，货架上的数量并不会减少；而倒序遍历则像是先把货架上已有的存货用掉，再补新货，确保每一轮最多只拿一次。这个类比可能不完全严谨，但这个“先读旧值、再写新值”的思想，正是理解背包优化的一把钥匙。

3.3 一维化之后的状态语义变化

一维化之后，dp[j]的含义其实是“在考虑当前已经枚举过的物品时，容量为j能获得的最大价值”。它不再是“前i件物品”，而是“当前一层循环后的状态”。因为数组被复用，dp[j]既包含上一轮的结果，也可能包含本轮已经更新的结果——一切取决于遍历方向。

这也就解释了为什么在完全背包中，我们要刻意使用正序遍历：我们希望同一件物品可以被多次选取，因此更新后的dp[j-w[i]]可以被后续更大容量的状态使用。这个对比非常清晰：

• 0/1背包：一维数组倒序遍历，保证每个物品最多选一次。
• 完全背包：一维数组正序遍历，允许每个物品无限次选取。

从代码上看，两者只差一个遍历方向的差异，但语义截然不同。如果不能从原理上理解，只靠背模板很容易在写变体时出错。

3.4 滚动数组版本的使用场景

一维数组本质上就是滚动数组的一种特殊形式。如果你觉得从二维直接跳到一维不太适应，也可以先写两层数组但只保留两行，即用dp[2][W+1]，在循环中通过i%2来切换行。这个版本写起来稍麻烦，但能帮你建立“当前行依赖上一行”的直觉，之后再看一维版本就会很自然。

我在实际调试背包类题目时，有时会先写二维版本，用来和滚动数组版本对拍。这种对拍策略对验证算法正确性非常有用。即使你在面试或竞赛中最终交的是一维代码，你在草稿纸上推演时也建议先画出二维表格，填一遍表，再做空间压缩。这个习惯能大幅降低状态转移写错的风险。

4. 从0/1到完全背包：正序遍历背后的逻辑

4.1 完全背包与0/1背包的差异

完全背包和0/1背包唯一的区别在于：每件物品可以无限次选取。这个“无限”听起来像是个巨大的状态空间，但动态规划处理它的方式异常简单——只需要改变容量遍历方向。

0/1背包一维版本需要从大到小遍历容量，以避免同一件物品被重复选取；完全背包则恰恰需要从小到大遍历容量，以允许重复选取。我们上节已经看过例子，这里再把完全背包的代码贴出来：

def knapsack_complete(weights, values, W): dp = [0] * (W + 1) n = len(weights) for i in range(n): for j in range(weights[i], W + 1): dp[j] = max(dp[j], dp[j - weights[i]] + values[i]) return dp[W]

同样只有一行遍历顺序不同，结果却完全不同。这个差异正是理解背包问题变体的关键所在。

4.2 为什么正序遍历可以实现无限选取

继续用刚才的例子：一个物品重量2、价值3，背包容量4，完全背包的目标是“最多能取多少件这个物品”。正序遍历时：

• j=2：dp[2] = max(dp[2], dp[0]+3) = 3
• j=3：dp[3] = max(dp[3], dp[1]+3) = 3
• j=4：dp[4] = max(dp[4], dp[2]+3) = max(0, 3+3) = 6

在j=4这一步，dp[2]已经包含了“取了这个物品一次”的价值3，所以dp[4]再加一次3，就变成了取两次，总价值6。在这道题中，容量4正好能装下两个重量2的物品，因此结果正确。

这说明正序遍历在j递增的过程中，当前物品的“新状态”可以被后续更大的容量状态直接引用，从而实现了“同一件物品可以被连续取多次”的效果。它的本质是状态更新具有了传递性，而不是严格依赖上一轮的旧值。

4.3 多重背包：二进制拆分的经典套路

多重背包是介于0/1和完全背包之间的问题：每件物品有数量限制c[i]，最多可以取c[i]次，但不能无限取。

一个朴素的思路是：把每件物品复制成c[i]份，然后当作0/1背包处理。这种做法的复杂度是O(n * c[i] * W)，当c[i]很大时完全不可行。

标准解法是对物品数量做二进制拆分。原理是：任意一个正整数c，都可以拆分成若干个2的幂次之和，最多拆出log2(c)个。用这些拆分出来的“物品组”可以组合出1到c之间的任意数量。

举个例子：某物品数量c=13，可以拆成1、2、4、6（因为1+2+4=7，剩余6）。用这些组可以表示1到13中的任意取用数量，比如取5件就是4+1，取9件就是8+1（实际这里用6+2+1），总之没有遗漏。拆出来的每组看作新物品，重量等于原来重量乘以组大小，价值等于原来价值乘以组大小，然后跑0/1背包即可。

代码可以这样写：

def knapsack_multi(weights, values, counts, W): new_weights = [] new_values = [] n = len(weights) for i in range(n): cnt = counts[i] k = 1 while k <= cnt: new_weights.append(weights[i] * k) new_values.append(values[i] * k) cnt -= k k *= 2 if cnt > 0: new_weights.append(weights[i] * cnt) new_values.append(values[i] * cnt) return knapsack_01_1d(new_weights, new_values, W)

拆分的原理是“以数量为单位进行状态合并”，它是背包问题中一个很典型的数论技巧。我在竞赛中多次用到这个方法，几乎不需要额外记忆其他版本。

4.4 混合背包的工程化处理

实际题目中还有一种常见情况：不同物品的类型不一样，有些只能取一次（0/1），有些可以无限取（完全），有些有数量限制（多重）。这就是混合背包问题。

处理方式并不复杂：遍历每一件物品时，根据它的类型走不同的分支。如果是0/1背包，就倒序更新；如果是完全背包，就正序更新；如果是多重背包，先用二进制拆分成若干个0/1物品，再走0/1分支。严格来说，只要处理顺序正确，这些分支可以在同一个dp数组上累计结果，因为dp数组的状态语义是统一的。

逻辑上看起来麻烦，但理解了底层原理后反而简单。关键不在于背代码，而在于理解每种背包“为什么用这个遍历方向”，然后顺着语义去组合。

5. 背包问题的变形扩展：从求最大价值到求方案

5.1 恰好装满与不超过容量：初始化差异

我前面提到的“恰好装满”变体在笔试题中出现频率很高。它的状态定义依然是“在容量为j时的最大价值”，但初始化的语义变了。

如果要求“不超过容量”，dp[j]初始为0即可，因为就算什么都不选，在任意容量下也是合法状态，价值为0。

如果要求“恰好装满”，那么dp[0] = 0表示容量为0时不需要任何物品就可以满足；dp[1..W] = 负无穷表示这些容量无法由0件物品凑出来，即不可达状态。负无穷通常用一个很大的负数表示，比如-10**9，以免在相加时溢出到正数范围。

这种差异在求“最少物品数”“方案数”的时候也会出现。比如“凑零钱”类问题其实就是一个完全背包求最少硬币数，它的初始化就是dp[0]=0，其余为无穷大，因为你要从空状态出发去凑出目标金额。

5.2 求方案数：dp数组由最大值改为计数

另一个高频变体是“求方案总数”，比如给定容量W和物品，问有多少种方式能恰好装满背包。

这时候dp[j]的含义从“最大价值”变成了“方案总数”。初始化为dp[0] = 1，其余为0。转移方程也不是取max，而是累加：dp[j] += dp[j - w[i]]。

这里有两个容易出错的地方。第一，累加时是否需要去重取决于题目是“组合数”还是“排列数”。如果外层循环物品、内层循环容量，得到的是组合数（不同顺序不重复计数）；如果外层循环容量、内层循环物品，得到的是排列数（不同顺序算不同方案）。这个细节经常被拿来出题，值得格外注意。

第二，如果题目还要求“装满”，初始化dp[0]=1，而不是把所有dp[j]都初始化为1。否则空方案会被错误地计入所有容量中。

5.3 输出具体选法：路径回溯

有些场景不仅要求最优价值，还要求输出具体选了哪些物品。这类问题需要在计算dp时额外记录决策路径。

一个常用方法是用一个二维布尔数组或整型数组choice[i][j]来记录：在更新dp[i][j]时，当前你选择了“不放”还是“放”，或者进一步记录“放入了第i件”。当dp表全部算完后，从dp[n][W]开始回溯：

• 如果choice[i][j]标记为“放入”，则将第i件加入结果集合，并将容量j减去w[i]，接着看dp[i-1][j-w[i]]。
• 否则直接看dp[i-1][j]。

需要注意的是，如果使用一维数组优化，就没办法轻易记录二维决策路径了，因为历史信息已经被覆盖。对于需要回溯的题目，保留二维数组更稳妥。我个人的建议是：在面试或作业场景中，不要为了追求空间优化而牺牲可解释性，除非题目明确要求空间复杂度。

5.4 二维费用背包：不止一个容量约束

还有一种扩展是每个物品有两种费用，比如重量和体积，背包也有两个容量上限。状态相应地变成三维：dp[i][j][k]表示考虑前i件物品，第一种容量为j、第二种容量为k时的最大价值。空间优化后可以变成二维数组dp[j][k]。

二维费用背包最麻烦的是循环顺序。优化到二维dp后，两个容量的枚举方向都要跟0/1背包一样采用倒序，否则同一件物品会被重复使用。很多人在这个点上出错，因为他们只记得“容量要倒序”，却忘了这里有两个容量，两者都要倒序。

写代码时常见的错误是只把j倒序，k却正序。我调试过好几次这种问题，最终排查方法很简单：把二维版本写出来对拍，或者盯着转移方程，确认dp[j][k]依赖的都是旧状态。

5.5 分组背包与依赖背包

分组背包：物品被分成若干组，每组最多选一个。处理方式是外层循环组，中层循环容量，内层循环组内物品。容量循环必须放在组内物品循环之前，否则无法保证“每组最多选一个”。

依赖背包：某些物品必须先选前置物品才能选，比如买主板才能买CPU。一般通过将依赖关系转化为分组背包或树形DP处理。这类进阶内容，在掌握了基础背包后再去研究会更顺畅。

这些扩展问题都有一个共同点：核心依然是“状态定义 + 转移 + 遍历顺序”。只要基础打牢，这些变体并不会额外增加太多理解成本。

6. 背包问题的调试与常见错误

6.1 滚动数组顺序错误

这是我见过最频繁的错误。一维0/1背包写成正序遍历，或者完全背包写成倒序遍历，结果都会偏离正确答案。症状通常是：0/1背包结果偏大（物品被重复选取），完全背包结果偏小（每种物品最多取了一次）。

排查方式很直接：构造一个单物品的小数据，比如重量2价值3，容量4。如果0/1背包得出6，说明遍历方向错了。这种小样例几乎是背包调试的“试金石”。

6.2 初始化搞混导致的结果偏差

“不超过容量”和“恰好装满”初始化结果差异巨大。如果题意要求恰好装满，但你把dp都初始化为0，那么结果可能会高，因为一些“并未装满”的状态也被纳入比较；如果题意只是不超过容量，但你用了负无穷初始化，那么你可能会得到错误的负值或不可达状态，因为dp[0]=0但dp[1]=-INF，状态并没有完全连通。

我的建议：做题前先明确题目说的是“恰好装满”还是“最多装这么多”。如果是后者，初始化0基本没错；如果是前者，除了dp[0]，其余全部初始化为一个极小的负值。

6.3 边界条件遗漏：忘记判断j >= w[i]

在二维版本中，如果j < w[i]时没有把dp[i][j]继承为dp[i-1][j]，而是直接跳过了，那么dp[i][j]可能仍保留为0，导致后续比较出错。一维版本中，倒序遍历的起点是W，终点是weights[i]，循环条件中的weights[i] - 1一定要写对。写成W >= 0虽然也能跑，但会多做很多无意义的比较，且可能引用到容量为负的dp状态。

6.4 常见错误速查表

6.5 一个很实用的调试技巧：对拍

我在练习阶段最常用的方法是写两个版本：一个是最直观的二维DP，另一个是优化后的一维DP，然后随机生成小规模数据，用两个版本跑同一份输入，对比输出和中间表。如果中间表一致，几乎可以确认优化版本没有改坏逻辑；如果不一致，就打印中间状态，定位第一个出现偏差的位置。

这个对拍技巧不仅适用于背包，也适用于几乎所有动态规划题目。它比只靠看代码找错要快得多，尤其当数据量一大，肉眼根本盯不过来。

按我个人经验，背包问题的学习曲线其实很陡，但它带来的收益很高。理解清楚0/1背包的一维化为什么倒序、完全背包为什么正序之后，你再去写“凑零钱”“分割等和子集”“最后一块石头的重量”这些题，都会有一种“这不就是背包换个马甲”的感觉。最后再分享一个小建议：练习时不要只背模板，一定要自己动手在纸上填一张小规模DP表，试着标出每个状态是从哪个旧状态转移来的，这些看似琐碎的动作才是真正把动态规划内化的方式。