0/1背包问题详解：动态规划、状态转移方程与滚动数组优化

1. 问题定义与动态规划的整体思路

1.1 0/1背包问题的数学描述

0/1背包问题（0/1 Knapsack Problem）是算法学习路上绕不开的一道经典门槛。简单来说就是：有一个背包，容量为 W，面前有 n 个物品，第 i 个物品有自己的重量 wi 和价值 vi，每个物品只能整件拿走或者放下，不允许切割，也不允许重复拿。目标是在不超过背包容量的前提下，装进背包的物品总价值最大。

“0/1”这个名字就来源于每个物品只有两个状态：0 表示不选，1 表示选。

举个例子：背包容量 10 kg，有 4 件物品，重量分别是 2、4、3、5 kg，价值分别是 3、5、4、8 元。你该怎么选？这个例子我在后面会一步一步手动推导填表，现在先记住这个输入，后面全程用它做演示。0/1 背包问题看起来很直观，但真正难住很多人的地方在于：物品数量一多，“选或者不选”的组合数会爆炸式增长。每个物品有两种选择，n 个物品就有 2 的 n 次方种组合，暴力枚举在 n 稍大时就完全不可行。

我还在做学生的时候，第一次看到这个问题，第一反应就是“把所有组合列出来比较大小”。等真去实现的时候才发现，n = 30 就要枚举 10 亿级别种情况，这还没算上筛选超重方案的逻辑。可见暴力不是办法，我们真正需要的是一种能复用中间结果、避免重复计算的求解思路，这就是动态规划登场的时机。

1.2 为什么不能直接贪心

很多刚接触背包问题的人都会问：我按“单位价值（价值 / 重量）”从高到低排序，先塞性价比高的，不就行了吗？在一些允许切割物品的分数背包问题（Fractional Knapsack）里，贪心确实是正确答案，因为你可以把最后一块物品切开补满剩余容量。但 0/1 背包不允许切分，贪心的短视就会立刻暴露。

我构造一个非常经典的反例：背包容量 50，有三件物品，物品 A 重量 30 价值 60，物品 B 重量 20 价值 100，物品 C 重量 30 价值 120。按单位价值排序的话，B 的单位价值是 5，最高，先选 B；剩余容量 30，再选 A（单位价值 2），总价值 160。但聪明的读者已经看出来了，直接选 B + C，总价值是 220，比贪心的 160 高出一大截。

问题出在哪里？贪心只考虑了“局部最优”，但 0/1 背包的每个选择都会占用容量，这个容量占用可能堵死后续更有价值的组合。也就是说，一个物品的价值不能脱离“剩余容量”来单独评价。这个观点很关键，它在动态规划里直接对应了“把容量作为状态的一维”这一设计。不理解这句话的人，看状态转移方程容易一头雾水，理解了这句话，整个背包问题的思路就顺了。

1.3 动态规划的核心思想：最优子结构

动态规划能解决 0/1 背包问题，依赖的是“最优子结构”这个性质：原问题的最优解，可以由子问题的最优解推导出来。

具体来说，假设我们已经处理完了前 i-1 个物品，并且知道在任何容量 j 下的最优价值 dp[i-1][j]。现在来了第 i 个物品，这个物品只有两种命运：不选它，那么前 i 个物品的最优价值还等于前 i-1 个物品的最优价值；选它，那么我们必须先腾出它的重量 wi，也就是说要从前 i-1 个物品在容量 j-wi 下的最优方案转移过来，然后加上这个物品的价值 vi。

两种选择哪个好，就取哪个，这就是“动态规划的核心决策模型”。大问题被拆成了两个独立的子问题，每个子问题又继续往下拆，直到“没有物品可选”或“容量为 0”的边界。这种层层拆解和复用的方式，避免了暴力枚举里天文数字般的重复计算。接下来的章节，我会把这种思路落地成具体的状态定义和转移方程，这才是真正需要动手的地方。

2. 状态定义与状态转移方程推导

2.1 dp[i][j] 的含义与维度设计

要写动态规划，第一步永远是“定义状态”。状态定义得好不好，直接决定代码是妙手还是灾难。对于 0/1 背包问题，绝大多数教材都会用二维数组：dp[i][j] 表示“从前 i 个物品中挑选，总重量不超过 j 时，能获得的最大价值”。

这个定义里藏着两个维度，前 i 个物品是“决策的进度”，它告诉我们已经考虑了哪些物品；容量 j 是“当前背包的剩余限制”，它告诉我们还能放多重的东西。为什么要容量也作为一维状态？因为前面的例子已经解释了，物品的组合价值高度依赖剩余容量。假如只记录“前 i 个物品能获得的最大总价值”这么一个一维数组，那么我们在判断第 i 个物品放不放时，根本不知道背包还剩多少容量，决策也就无从谈起。

状态定义里的一个常见理解障碍是“前 i 个物品”到底什么意思。注意，这里说的“前 i 个”不是指某一种固定选择顺序，而是说我们从 n 个物品中任意取前 i 个作为候选集合。我们在填表时是一行一行往下推的，每推一行就多一个候选物品，相当于把一个大问题切成了 n 层子问题。

我习惯把 dp 表想象成一个二维表格：行是物品序号，列是容量从 0 到 W，格子里的数字就是“在当前行和当前列限制下的最优价值”。接下来的状态转移方程，就是在回答“这个格子里的数字是怎么从上一行算出来的”这个问题。

2.2 状态转移方程的两条分支

有了 dp[i][j] 的定义，转移方程就水到渠成了。考虑第 i 个物品（注意代码里 item 下标从 1 开始编号时，对应的物品重量是 wi，价值是 vi），在容量为 j 时：

如果 j < wi，也就是说当前容量连这个物品本身都装不下，那没得选，只能不选：dp[i][j] = dp[i-1][j]。

如果 j >= wi，我们需要在两种决策中取最大值：

• 不选第 i 个物品；此时结果就是 dp[i-1][j]
• 选第 i 个物品；此时我们从“前 i-1 个物品、容量 j-wi”的状态转移过来，再加上 vi，也就是 dp[i-1][j-wi] + vi

用一个公式把两种情况合并起来就是： dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + vi)，其中 j >= wi 时第二个选项才合法。

我为什么特别强调第二项必须从 i-1 行转移过来？因为这是 0/1 背包“每个物品只能用一次”在数学模型上的直接体现。如果允许从 dp[i][j-wi] 转移，那意味着同一个物品可以被连续装入多次，问题就退化成完全背包了。这一点在二维实现里看不出太大的问题，但后面讲到一维滚动数组优化时，将是决定代码对错的胜负手。

给一个直观的解释：dp[i-1][j-wi] + vi 表达的意思是“我在没有第 i 个物品的任何参与下，用 j-wi 的容量做到了最优，现在把这个物品塞进去，正好把容量填到 j，价值也增加了 vi”。整个过程中第 i 个物品只出现了一次，而且是作为“当前正在决策的物品”出现的，这就是 0/1 的语义。

2.3 手工推导一张完整的 dp 表

光看公式容易发虚，我建议每个学背包问题的人都亲手填一次表。这里就用开头那个例子：容量 W=10，4 件物品分别是 物品1（w=2, v=3）、物品2（w=4, v=5）、物品3（w=3, v=4）、物品4（w=5, v=8）。

初始化：dp[0][j] 全部等于 0，因为前 0 个物品没有任何东西可选，价值自然为 0，无论容量多大。

第 1 行（只考虑物品1）：容量 j=0、1 时，装不下重量 2 的物品，所以价值是 0；j=2 到 j=10，都装得下物品1，所以价值统一变成 3。这一行填下来是：0 0 3 3 3 3 3 3 3 3 3。

第 2 行（考虑物品1和2）：j=0、1 时是 0；j=2、3 时只能选物品1，所以是 3；j=4、5 时，比较“不选物品2（3）”和“选物品2（0 + 5）”，选后更大，所以是 5；从 j=6 开始，容量足够同时容纳物品1和2（2+4=6），价值 3+5=8，直到容量 10 都是 8。这一行是：0 0 3 3 5 5 8 8 8 8 8。

第 3 行（加入物品3，w=3, v=4）：我没有必要把每个格子都重新“拍脑袋想”，只需要从上一步的 dp[2] 行查表。比如 j=7 时，不选物品3看 dp[2][7]=8；选物品3则看 dp[2][4] + 4 = 5 + 4 = 9，所以取 9。j=9 时，不选是 8；选则是 dp[2][6] + 4 = 8 + 4 = 12，取 12。填完这一行：0 0 3 4 5 7 8 9 9 12 12。

第 4 行（加入物品4，w=5, v=8）：最后一个关键格是 dp[4][10]。不选物品4是 dp[3][10]=12；选物品4则是 dp[3][5] + 8 = 7 + 8 = 15。最终答案就是 15。完整表格看下面：

我强烈建议你在纸上重新画一遍这张表。填表的过程就是练“查表”的手感，以后见到任何动态规划题目，第一反应应该是“我能不能把决策拆成两半，并且用一个状态数组把它们连起来”，而不是“我该套哪个公式”。

3. 完整代码实现与参数计算过程

3.1 朴素二维动态规划代码

状态定义和转移方程确定以后，代码就是照葫芦画瓢。以下用 Python 实现一个最朴素的二维版本，为了贴合大多数读者的习惯，我对物品数组从下标 0 开始，因此在循环里用 i-1 去访问第 i 个物品的重量和价值：

def knapsack_2d(weights, values, capacity): n = len(weights) # 多开一行一列，行0表示没有物品，列0表示容量为0 dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): w = weights[i - 1] v = values[i - 1] for j in range(1, capacity + 1): if j >= w: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v) else: dp[i][j] = dp[i - 1][j] return dp[n][capacity]

这个版本的时间复杂度是 O(n * W)，空间复杂度同样是 O(n * W)。为什么时间是这个量级？因为外层有 n 个物品，内层容量从 1 到 W 逐个枚举，每个格子里的操作都是 O(1) 的查表与比较，总共就是 n 乘以 W 次操作。这也是背包类问题区别于暴力枚举的核心优势：把指数级的组合爆炸压缩成了多项式级。

有一点值得说明：内层循环为什么从 j=1 开始而不是从 j=w 开始？这是为了代码可读性，容量为 0 的格子永远为 0（装不下任何正重量物品），而且 dp[i-1][1] 这些“不够容量”的格子只能从前一行的同列继承。从 1 开始循环时，j < w 的分支会覆盖这些继承逻辑，逻辑上更完整。当然，如果你想写得紧凑一点，也可以让 j 从 w 开始循环，把 j < w 的情况留给初始化时的零值，不过初学者建议保留完整分支，逻辑更清晰，也更容易调试。

3.2 滚动数组优化原理

二维 dp 表里有个明显的可优化点：我们计算第 i 行时，只用到了第 i-1 行的数据，再往前的行根本不会再被使用。那为什么还要保存所有历史行呢？不需要。我们完全可以用一个一维数组 dp[j]，每轮循环只维护“当前容量 j 下的最优价值”，然后在处理第 i 个物品时，把这个一维数组原地更新。

这个技巧在动态规划里有个专门的名字，叫滚动数组（Rolling Array）。说白了，我们不关心过程，只关心结果。之前用二维表可以回溯出具体选哪些物品，但如果只求最大价值，滚动数组足够用了。

实现思路：遍历每个物品，然后从容量 capacity 往 0 方向逆序更新一维数组。为什么必须逆序，这可能是整个 0/1 背包里最容易出错、也最值得深究的一个细节，下一节单独讲。

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

空间立刻从 O(n * W) 降到了 O(W)，时间还是 O(n * W)。在容量上万、物品上千的场景里，这个节省是非常可观的。比如某次我在一台内存受限的设备上跑一个十亿级资产配置的小模型，二维表直接让内存爆掉，改成滚动数组之后内存占用从几 GB 掉到了几十 MB，这就是优化的现实意义。

3.3 一维逆序更新的原理，写错就是完全背包

很多人背下了“逆序”这个结论，却不知道为什么。我举一个最简单的例子来说明。

假设只有 1 件物品，重量 1，价值 2，背包容量 2。正确的结果应该是最大价值 2，因为这件物品只能选一次。如果此时我们用正序更新一维数组：

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

这下就出问题了。dp[2] 算出来 4，相当于“同一件物品被装了两遍”。原因在于，正序更新到 j=2 时，dp[1] 已经不是上一轮的状态，而是已经被当前物品更新过的新值。dp[1] = 2 表示“容量 1 已经选了这个物品”，然后我再尝试在容量 2 里再装一次它，相当于物品被重复使用了。

改成逆序以后：

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

dp[2] = 2，完全正确。

一句话总结：正序遍历会让当前物品在当前轮次被多次使用，这恰好是“完全背包”的语义；逆序遍历则保证每个物品只参与一次状态更新，这是“0/1 背包”的语义。我在面试候选人的时候，喜欢故意在这里设问，能把这个原因讲清楚的人，说明是真的理解了动态规划的细节，而不是背代码。

3.4 轨迹回溯：从 dp 表倒推选了哪些物品

求出了最大价值还不够，很多实战场景里我们还要知道“到底是哪几个物品被选中”。这个需求用二维 dp 表做起来非常直观，思路是从最后一个物品往第一个物品反向追溯：

• 如果 dp[i][j] == dp[i-1][j]，说明第 i 个物品没有被选，因为我们跳过它也能达到同样的最优价值。
• 如果 dp[i][j] != dp[i-1][j]，说明第 i 个物品被选了，因为状态转移时它贡献了额外的价值，此时把容量 j 减去 wi，继续往前追溯。

用代码实现就是：

def knapsack_traceback(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): w = weights[i - 1] v = values[i - 1] for j in range(1, capacity + 1): if j >= w: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v) else: dp[i][j] = dp[i - 1][j] # 回溯 selected = [] j = capacity for i in range(n, 0, -1): if dp[i][j] != dp[i - 1][j]: selected.append(i) j -= weights[i - 1] selected.reverse() return dp[n][capacity], selected

回溯为什么能用“两个值是否相等”来判断选没选？这就涉及一个细节：dp[i][j] 一定大于等于 dp[i-1][j]，因为多考虑一个物品只会让结果更好或持平。它严格变大，只可能是选入第 i 个物品带来了额外价值。当然，有一个特殊情况需要留意：如果出现了价值为 0 的物品，或者物品价值本身是负值，这个等值判断就可能出错。届时要额外处理，比如记录一个布尔数组 decision[i][j] 来标记每次转移来自哪一个分支。这个问题我们在下一章的“常见问题”里会继续展开。

4. 常见错误、易错点与调试技巧实录

4.1 一维滚动数组的顺序问题，是最典型的错误

我在给团队新人做代码评审的时候，见过最多的错误就是内层循环写成正序。正序的后果上面已经讲过，会让 0/1 背包变成完全背包，结果偏大。这个 bug 最坑的地方在于：它不是直接崩掉，而是给出一个“看起来差不多但其实是错的”数值。小规模数据下错误可能不太明显，一旦容量变大、物品种类变多，偏差会越来越离谱。

怎么快速自查？两个办法。第一个，拿容量等于某个物品重量的两倍的简单用例去试，如果结果里出现了物品重复选择导致的价值翻倍，那就是顺序写反了。第二个，打印整个 dp 数组，观察是否出现“同一物品在同一轮里连续更新”的特征。我在调试时习惯在内层循环里临时插入一行打印，把每次循环前后的 dp 数组打出来对比，问题立刻水落石出。

值得小心的是，并不是所有题都要求逆序。如果你基于完全背包改造，正序反而是正确写法。所以不要死记“动态规划就一定要逆序”，而要理解你所写的那一题对“物品使用次数”的语义要求。

4.2 初始化 0 还是负无穷，对应“是否必须装满”

普通的 0/1 背包问题，比如“容量不超过 W 时最大价值是多少”，dp 数组全部初始化为 0 是正确做法，因为“什么都不装”总是一种合法方案，价值为 0。

但有一种常见变体问的是“恰好装满背包时，最大价值是多少”。如果没法恰好装满，那答案就不是 0，而是“不可能”。这时候 dp 数组的初始化就得改为：dp[0] = 0，dp[1..W] = 负无穷。为什么？因为容量 0 是唯一一个“不用任何物品就能达到”的状态，其他容量一开始都没有任何合法方案，用负无穷标记“方案不存在”。之后每做一次转移，都是在一个合法子状态上追加一个物品，最终 dp[W] 若是负无穷，就说明装不满。

我举个例子：容量 5，物品重量 2 和 4，价值均为 1。不加区分的话，普通 0/1 背包容量 5 时最大价值是 1（选重量 4 的）；但“恰好装满”的版本下，没有任何物品组合的重量能精确等于 5，答案应该是“不可行”。如果用普通初始化，返回 1 就是误导。初始化这个细节在笔试和面试里经常被故意挖坑，尤其是题目描述里写着“恰好”这两个字的时候，我建议你第一时间检查初始化逻辑。

4.3 边界输入：重量为 0、价值为负的奇妙情况

实际工程项目里的数据不像算法题那么干净。比如物品重量可能为 0。重量为 0 且价值为正的物品，在现实里确实罕见，但在这个抽象模型里有可能出现。如果重量为 0，物品的价值应该被无限制地加入，因为装它不会占任何容量，也不会违背 0/1 的定义——它确实只被选了一次，只不过容量对它从来不构成约束。但在普通的一维滚动数组循环里，w=0 时内层循环的终止条件要小心处理，否则会无限循环或出现意料之外的结果。我的建议是先单独处理重量为 0 的物品：把它们的总价值直接加入答案，然后从物品列表中移除。

价值为负的物品则要反过来想：一个物品重量占地方，价值还倒扣，那它永远不值得选。但有一个经典陷阱：如果题目额外要求“必须选满 k 件物品”，负价值物品就可能不得不被选进来。这时 dp 数组就不能只存“最大价值”这一个值，可能得升级成“二维 DP”，用 dp[i][j] 表示前 i 个物品选了 j 件的最优价值。总之，读到“必须”“恰好”“至少”“不超过”这些限定词时，都要逐字审视它对状态定义的影响。

4.4 当容量超大时，O(n*W) 撑不住了怎么办

动态规划的时间复杂度跟容量 W 直接相关，这在大多数题目里没问题，但一旦 W 达到 10 的 9 次方这种量级，O(nW) 的思路就直接报废。比如某次我在处理一个数据中心迁移计划时，网络带宽总量是一个极大的数字，而任务数量只有几十个，常规背包循环根本跑不完。

行业里有几种替代方案。第一种是“按价值 DP”：把 dp 定义为“获得总价值 v 时所需的最小重量”，然后遍历所有价值总和范围内找最小重量不超过 W 的最大 v，复杂度 O(n * V)，V 是所有物品价值之和。当价值范围远小于容量范围时，这一招很管用。第二种是分治/折半枚举（Meet-in-the-Middle）：把物品分成两半，各自枚举所有组合，再用双指针合并，复杂度 O(2^(n/2) * n)，适合 n 较小但容量很大的场景。第三种是放弃精确解，用贪心或遗传算法求近似解，工程上经常够用。我个人的建议是：拿到题目先估一下 n 和 W 的量级，再决定用哪种策略，而不是无脑套二维 dp。

5. 实际工程应用与变种延伸

5.1 生产环境中的真实案例：资源分配与任务取舍

0/1 背包问题在工程上并不是“纸上谈兵”。举一个我实际经历过的场景：某公司的离线计算集群，每天深夜会收到一批数据处理任务，每个任务有固定的内存和 CPU 占用，以及一个“收益值”，通常是对应的业务优先级或预估处理量。集群总资源有限，每个任务只能整体执行或跳过，不能切割。这不就是一个标准的 0/1 背包问题吗？任务列表是物品，资源总量是背包容量，收益是价值，只不过我们把“重量”换成了“内存/CPU 占用”，“价值”换成了“业务收益”。

第一版实现我直接用二维 dp 表，任务数量 3000 个，资源总量按 GB 粒度划分，结果发现数组的列数撑到了几十万，内存直接爆掉。后来改成滚动数组，把资源粒度从 1GB 改成 4GB，再对任务做一轮“超重预筛选”，空间与时间立刻变得可用。这个经历让我体会到，动态规划代码写出来只是第一步，能不能在真实资源约束里跑起来，才是工程上的真正门槛。

还有一类高频场景是“项目预算取舍”：预算上限是容量，每个候选项目有成本与预期回报，选项目就是一个 0/1 背包决策。需要说明的是，真实业务里往往会有“项目 A 和项目 B 必须二选一”之类的限制，那就超出基础模型的表达了，需要往树形背包或依赖背包方向扩展，但核心的状态定义逻辑依然一脉相承。

5.2 完全背包与多重背包，以及二进制拆分

0/1 背包是所有背包问题的基础。有三种最经典的变体，它们之间的差别只在“每个物品能用几次”：

• 0/1 背包：每个物品最多选一次。核心实现是一维数组倒序遍历。
• 完全背包：每个物品无限次可用。核心实现是一维数组正序遍历，因为每次更新都可以基于当前物品已经被选过的状态继续进行。
• 多重背包：每个物品有数量上限，比如物品 i 最多能用 ci 次。一种通用做法是二进制拆分：把 ci 个同种物品拆成若干个“打包物品”，每个打包物品的重量和价值分别是原物品的 1 倍、2 倍、4 倍……直到余数，然后把这些打包物品当作 0/1 背包中的独立物品来处理。

为什么拆成 1、2、4、8 这种 2 的幂次分组是合理的？因为任意一个不超过 ci 的正整数，都能表示成若干个 2 的幂之和，这就等价于我们可以在新的一组虚拟物品里组合出“实际取 k 个原物品”的任何方案。比如 ci=10，可以拆成 1、2、4、3 四个虚拟物品，四个虚拟物品的组合恰好能表示取 0 到 10 任意个数。这个技巧在我看来非常巧妙，它把“带次数限制”的复杂问题又拉回到了最基础的 0/1 背包模型上。

5.3 面试与竞赛里的高频考法，以及我的刷题顺序建议

背包问题在算法面试里出现频率常年居高不下，但真正的考察重点并不是让你默写模板。我见过最常考的几种变体是：求恰好装满背包的方案总数（此时 dp[j] 表示方案数，初始 dp[0]=1，转移方程变成 dp[j] += dp[j-w]）；求“最少的物品数达到目标价值”；以及“在价值与重量都有限制时的双维度背包”。

我自己带新人刷题时推荐的顺序是：先手推 3 到 5 个小型样例的 dp 表，完全搞清楚二维表的每个格子怎么填；再实现一维滚动数组版，并刻意在某道题里把正序和逆序各写一遍，对比两种输出的差异；然后做“恰好装满”和“方案数”两个变体；最后再尝试自己实现多重背包的二进制拆分。按这个顺序走下来，背包问题的基本功会非常扎实，遇到陌生变体也不会慌。

还有一个从实战里总结的小习惯：每次写背包问题的代码，先用 n=1 和 n=2 的小样例手工计算预期答案，再跑代码，对比一致后再放开规模。很多人一上来就跑大数据，代码错了也看不出问题在哪，只能靠一行行打印排查，效率很低。小样例是定位逻辑错误最好的工具，没有之一。

我个人在实际操作中的体会是，动态规划最难的从来不是“写出代码”，而是“从真实问题里读懂它的状态维度”。你面对一个新问题，如果能把“决策对象”和“限制条件”分别对应到状态的两个维度，这个题基本就解决了一大半。0/1 背包作为最经典的入门模型，恰恰是把这种思维训练得最扎实的练习。我在职场上做了几年之后回过头看，面试里考察背包问题，考察的就是候选人能不能从抽象描述里快速提取出状态转移关系，而不是背过几行模板代码。希望这篇长文能帮你真正打通这个模型，以后遇到任何背包类问题，都能一眼看穿它的本质。