0-1背包问题详解：二维DP、滚动数组与变体优化

背包问题是我入动态规划门槛时反复碰壁又反复顿悟的第一个模型。当年在学校里，老师讲“最优子结构”和“重叠子问题”，听得懂，但拿笔做题就懵。后来我把0-1背包问题从头到尾手推了三张表，才算真正把“递推”两个字刻进脑子里。如果你也属于“模板看得懂、题目不会做”这一类，这篇详解就是写给你的。我会以0-1背包为主线，讲清楚二维DP推导、滚动数组优化、完全背包与多重背包的差异、初始化陷阱、方案回溯，以及面对一道新题时怎么判断它到底是不是背包问题。中间会穿插大量上手代码和我在实际编码中踩过的坑，希望能帮你少走一些弯路。

1. 背包问题难在哪：贪心的直觉与穷举的天花板

1.1 问题描述其实很朴素

想象一个背包，容量为C，现在有n件物品，每件物品都有重量w[i]和价值v[i]。你的目标是在不超过背包容量的前提下，选择若干物品，使得总价值最大。

这就是0-1背包问题的原型。注意“0-1”这三个字：每件物品要么拿，要么不拿，不能切割，也不能重复拿。这和超市里可以随意重复拿苹果不一样，它更像是在挑选几件固定商品，每件商品只有一份。

为了后面方便手算，我固定用一组简单数据举例：背包容量C = 5，三件物品分别是：

• 物品1：重量2，价值3
• 物品2：重量3，价值4
• 物品3：重量4，价值5

肉眼就能看出，最优解是选物品1和物品2，总重量5，总价值7。但是怎么让程序也算出这个7，而不是靠直觉，这才是算法的意义。

1.2 贪心算法为什么不可靠

很多人第一反应是按“性价比”排序，也就是价值/重量最大的优先选。这个思路在日常生活中很常见，买股票、选理财产品时，大家总喜欢看收益率。然而背包问题恰恰是这个直觉的滑铁卢。

举个例子：背包容量50，三件物品分别为：

• 物品A：重量10，价值60，单位价值6
• 物品B：重量20，价值100，单位价值5
• 物品C：重量30，价值120，单位价值4

按单位价值从高到低排序，贪心会先拿A，再拿B，此时重量已经用了30，剩余20，拿不下C，总价值是160。但真正的最优解是直接拿B和C，重量50，总价值220。贪心只盯着局部最优，忽视了“给更重的物品腾出空间后可能更划算”这个全局约束。

这不是说贪心完全没用，只是没有通用的证明。遇到具体问题，如果找不到严格证明，最好别把宝押在贪心上。

1.3 穷举的空间为什么会爆炸

暴力枚举可以吗？可以，但是代价极其昂贵。每件物品有“选/不选”两个分支，n件物品就有2^n种组合。n=20时大约100万，勉强能算；n=30时超过10亿，已经很不现实；n=60时的量级更是夸张。这种指数级增长正是算法设计要解决的问题。

真正让人头痛的是另一件事：不同组合之间其实共享了大量中间结果。你选了物品1和物品2，和选了物品1、物品3后剩下来的容量，它们都在面对同一个问题：“剩余容量还能装多少价值”。如果每次枚举都重新计算这些子问题，就是在成倍地浪费已经算过的答案。动态规划的核心，就是把重复的子问题缓存下来，再按某种顺序逐个解决。

1.4 从0-1背包开始是最稳的学习路径

动态规划的题目千变万化，有区间DP、树形DP、状态压缩DP、数位DP等，但背包家族是最容易被抽象的模型之一。它直接对应现实中的预算分配、资源调度、任务选择，而且变体规律非常清楚：0-1背包、完全背包、多重背包、分组背包、依赖背包，都是在同一个骨架上改条件。先把最基础的0-1背包嚼烂，后面遇到复杂变体时，你至少知道该从哪个方向去调整转移方程。

2. 0-1背包二维DP：把决策表一笔一笔填清楚

2.1 状态定义：dp[i][j] 到底代表什么

二维动态规划第一步是定义一个状态。0-1背包里最常用的状态是：

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

这里有两个维度是有原因的：一个是“可选的物品范围”，另一个是“当前背包还能用的容量”。任何一个变了，最优解都可能变。比如同样只考虑前2件物品，容量4和容量5得到的最大价值就不同。

注意“不超过j”和“恰好等于j”是两种完全不同的定义，这一点在第五章会展开讲。现在先按“不超过”处理，因为它的初始化最简单：容量没用满也是一种合法状态。

2.2 状态转移方程：装与不装的二选一

当我们要把第i件物品加进考虑范围时，只有两种情况：

1. 不装这件物品。那么结果等同于只考虑前i-1件物品、容量不超过j时的最优值，也就是dp[i-1][j]。
2. 装这件物品。前提是j >= w[i]，装完后背包容量还剩j - w[i]，再从前i-1件物品中选出最大价值，也就是dp[i-1][j-w[i]] + v[i]。

两个方案取较大值，转移方程就写成：

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

这个方程是背包家族的“心脏”。你以后遇到的绝大多数背包变体，都是在调这两个分支的条件：要么把“拿不拿一次”改成“能拿无限次”，要么把“一次只能拿一件”改成“每件有数量限制”，但内层逻辑始终是这种多次选择。

2.3 手算一张表，胜过看十遍讲解

用上面的例子，背包容量5，三件物品分别是(2,3)、(3,4)、(4,5)。我们建一个(n+1) x (capacity+1)的二维表，初始全部是0。第0行表示一件物品都不考虑，不管容量多大，最大价值都是0；第0列表示容量为0，也装不下任何东西，值都是0。

先看第一件物品，重量2，价值3。容量0和1都装不下，所以保持0；容量2开始，可以装下，价值变成3；容量3、4、5同理，都是3，因为此时只有这一件可选，装下它之后没有别的物品可加。

第二件物品，重量3，价值4。容量0和1还是0；容量2时，装不下物品2，但可以装物品1，所以继承上一行的3；容量3时，两件中任意一件都能单独装下，选择价值更大的物品2，得4；容量4时，不装物品2则上一行是3（装物品1），装物品2则剩下容量1，不能再装物品1，所以也是4；容量5时，不装物品2则上一行是3，装物品2则剩余容量2，上一行在容量2时的最优值是3，于是总价值是4+3=7。这一行末尾的值就是7。

第三件物品，重量4，价值5，它的处理方式完全相同：容量4时可以单独装下物品3，价值5，大于上一行的3，所以更新为5；容量5时，装物品3剩下容量1，无法再装其他物品，价值5，而不装物品3可得到上一行的7，所以保持7。

最终递推结果和我们预想一致：最优价值是7。你看，整张表没有任何一步需要猜，每格都是由左上方的更小规模子问题推导出来的。

2.4 二维DP代码模板

理解表格后，代码就是机械翻译。注意下标偏移，用i-1访问物品数组：

def knapsack_01_2d(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(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*capacity)。当n和capacity都是几千时，表格还能接受；当二者到了10^5量级，这种写法直接爆内存。所以真正的比赛和工程实现中，很少直接用二维全表，除非后面的回溯方案需要它。

2.5 复杂度和应用范围

二维DP的时间复杂度是O(n*capacity)，空间复杂度是O(n*capacity)。capacity不一定是真正的“重量”，它可以是预算、时间、人数等一切被称为“限制条件”的量。因此，决定用背包DP之前，要先看一看这个容量上界有多大。如果capacity是10^9，但n又很大，普通背包DP就承受不了，可能需要换状态设计，比如用价值作维度。这个问题在最后一章会继续聊。

3. 滚动数组与一维优化：为什么0-1背包必须倒序遍历

3.1 滚动数组的动机：当前行只看得到上一行

观察二维转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])：算第i行时，真正用到的数据全是第i-1行的。第i-2行、第i-3行早就“退休”了，再留着它们纯属浪费。

所谓滚动数组，就是用一个一维数组反复覆盖自己：遍历完第i-1件物品后，数组里存的是“只考虑前 i-1 件物品”的状态；接下来要更新为“只考虑前 i 件物品”的状态，直接在原数组上改。这样空间就从O(n*capacity)降到了O(capacity)。

3.2 一维状态下标的意义

一维写法里，dp[j]的含义仍然可以理解为“容量不超过 j 时的最大价值”，只是在第i轮循环中它不断被更新。由于数组只有一维，无法再区分“上一行”和“当前行”，所以必须通过循环方向来保证计算依赖关系的正确性。

3.3 必须倒序遍历的原因：同一件物品不能被重复计算

这是0-1背包一维优化里最容易被问倒的问题：为什么内层循环要从capacity到w[i]倒着走，而不能从w[i]到capacity正着走？

用一个微型例子来说明。假设只有一件物品，重量2，价值3，背包容量4。一维数组初始化[0, 0, 0, 0, 0]。

如果正序遍历容量：

• 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[2]+3，此时dp[2]已经被更新成了3，于是dp[4] = 6。

这意味着什么呢？等价于你先把物品装进了容量2的背包，然后又看到容量4的背包，以为自己能再装一次这件物品，所以价值变成了6。可0-1背包中这件物品只有一件，无论如何不可能贡献6。这就是覆盖带来的灾难。

倒序遍历时：

• j=4用dp[2]+3，此时dp[2]还是初始的0，得到3；
• j=3用dp[1]+3，还是3；
• j=2用dp[0]+3，得到3。

整个过程只有一次成功拿取，完美符合“每件最多一次”的约束。倒序遍历的本质是：如果从小到大更新，dp[j-w]可能是本轮已经更新过的值，对应“第i件物品被拿了多次”；从大到小更新，dp[j-w]必然还是上一轮的值，正好对应dp[i-1][j-w]。

3.4 一维模板代码

0-1背包的一维代码极短，短到很多初学者背下来也不知道为什么：

def knapsack_01_1d(weights, values, capacity): dp = [0] * (capacity + 1) for i in range(len(weights)): 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]

推荐你把这个模板当成默认写法，但每次用之前都该在脑子里过一遍：为什么不是range(w, capacity+1)？为什么不是容量在外层？答得上来再用，不然出错时很难排查。

3.5 什么时候必须保留二维表

一维数组省了空间，但也丢了路径信息。如果只想输出最大价值，一维就够了；如果要输出具体拿了哪几件物品，就需要二维表，或者额外维护“选中记录”数组。后面第五章会讲回溯方案，这里先记住一个原则：只求价值可以用一维，要求方案就得加记录数据结构，不能把二维表一刀切扔掉。

4. 完全背包和多重背包：循环方向的语义突变

4.1 完全背包：物品无限次使用

把0-1背包的条件改成“每种物品都有无限件”，就成了完全背包。现实中的例子很常见：商品可以重复购买，预算有限，问最多能买多少价值的东西。

二维转移方程会变成：

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

注意第二项用的是dp[i]而不是dp[i-1]。区别就在这：0-1背包拿走这件物品后，只能在更小的“前 i-1 件”里选；完全背包拿走一件后，因为它可以无限供给，所以仍然可以在“前 i 件”里继续选。翻译到一维，就用正序遍历：

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

与0-1背包唯一的区别，就是把内层range(capacity, w-1, -1)改成range(w, capacity+1)。第一次看到这个差别时我也觉得很神奇：一个条件的变化，到头来只是循环方向反过来。

为什么不担心在同一轮里重复使用物品？因为那正是完全背包想要的效果。正序遍历允许dp[j-w]已经是本轮更新过的值，意味着同一件物品可以反复进入背包。如果你把完全背包的内层改成倒序，它反倒退化成0-1背包了。

4.2 0-1背包与完全背包的对比

最常把人绕晕的是两层循环的先后顺序。0-1背包一维写法是“外层物品，内层容量倒序”，完全背包是“外层物品，内层容量正序”。如果把0-1背包写成容量外层、物品内层，一维数组的状态语义就乱了，因为你在做dp[j]时不清楚当前使用的是哪件物品的更新。建议不要背“外层顺序口诀”，而是牢牢抓住一个判断标准：更新dp[j]时，dp[j-w]到底是上一轮的旧值，还是这一轮的新值。旧值等价于“这件物品还没被使用过”，新值等价于“这件物品已经能重复使用”。

我用一个常见场景来巩固认知：完全背包求最少硬币数量。给定硬币面额和总金额，问凑出总金额最少需要几枚硬币。这是“恰好装满”的完全背包，DP数组存储的是硬币数量而不是价值，初始化为大数，转移时做min(dp[j], dp[j-coin] + 1)。如果内层不小心写成倒序，就变成了每种硬币只能用一次，对硬币找零来说就是错的。

4.3 多重背包：从朴素三重循环到二进制拆分

多重背包介于两者之间：每种物品最多有cnt[i]件。朴素做法是把它当成0-1背包的扩展，每件物品额外循环使用次数：

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

这个写法时间复杂度是O(n * capacity * max_count)，数量上限很大时非常慢。更常用的优化叫二进制拆分。思想是：任意一个整数C都可以拆成若干个“2的幂”子集，使得从这些子集中选若干个，能组合出0到C的任意数量。比如C=13，拆成1, 2, 4, 6，这四个数通过选/不选，能凑出0到13的所有整数。于是不需要枚举每次取k件，只需要把每种物品拆成这些打包件，每个打包件变成0-1背包中的一件物品，然后直接跑0-1背包模板。

def knapsack_multiple_binary(weights, values, counts, capacity): items_w, items_v = [], [] for i in range(len(weights)): cnt = counts[i] k = 1 while cnt > 0: take = min(k, cnt) items_w.append(weights[i] * take) items_v.append(values[i] * take) cnt -= take k <<= 1 dp = [0] * (capacity + 1) for i in range(len(items_w)): for j in range(capacity, items_w[i] - 1, -1): dp[j] = max(dp[j], dp[j - items_w[i]] + items_v[i]) return dp[capacity]

比如某物品有13件，拆成1件、2件、4件、6件，第一包代表“取1件该物品”，第二包代表“取2件”，第三包代表“取4件”，第四包代表“取6件”。这些包任意组合就能覆盖0到13。取5件可以看成第一包加第四包。二进制拆分把O(count)的枚举压缩成了O(log count)，是不改变答案的正规优化。

4.4 混合背包和分组背包的快速上手

实际题里经常出现“有的物品只有1件，有的无限件，有的有限件”，这就是混合背包。常见做法是把01、完全、多重按类型分别套用不同的内层循环，或者把多重先二进制拆成0-1。分组背包则是每组物品最多选一件，本质上加了一维“组号”。这里不展开全部细节，但核心判断方法始终一致：问自己“同一物品在状态转移时能否被多次使用、是否属于同一组”，然后决定循环方向和状态维度。

5. 初始化、边界与方案回溯：细节才是真正的分水岭

5.1 “不超过容量”和“恰好装满”的初始化差了一整个数据类型

前面我用的都是“容量不超过 j 的最大价值”，所以dp初始化为0，因为容量空着不用也是一种合理状态。但有些题目要求“必须恰好装满背包”，比如硬币找零，这时你不能再把空着当合法状态，必须区分“可达”和“不可达”。

求最大值且恰好装满时，初始化成负无穷：dp[0] = 0，其他dp[j] = -inf。由于任何合法方案都需要从某个已可达状态转移过来，负无穷作为“不可达”的标记，会让错误的转移结果永远不占优。

求最小值且恰好装满时，反过来初始化成正无穷：dp[0] = 0，其他dp[j] = inf，转移时用min。如果最后dp[capacity]还是无穷大，说明无解。

这个细节决定程序的正误。我第一次写“恰好装满”的题目时，直接用全0初始化，算出来的结果居然也能通过一部分用例，但遇到无解或边界用例就全崩。原因就是全0会把同一件物品在“还没凑满”的状态上反复累加，掩盖了不可达状态。

5.2 常见边界：0件物品、0容量、0重量物品

背包题目里，n=0或capacity=0都很常见，正确代码应当能直接处理：

• 0件物品：二维表只有第0行，结果全是0。
• 0容量：只能不装任何物品，结果是0。
• 物品重量为0：这种物品可以免费增加价值。在0-1背包的倒序循环中，range(capacity, -1, -1)会覆盖到j=0，此时dp[0-w]就是dp[0]，会产生自引用累加。如果题意允许重量为0的物品，必须单独处理；如果题意不允许，也应该提前过滤掉，避免数据异常。

我不建议笼统地说模板永远正确，而是建议在每个具体题目里先问三条边界：物品为空、容量为0、有没有重量为0的物品。把这三种情况写测试用例跑一遍，代码基本就稳了。

5.3 回溯具体选取了哪些物品

当题目要求输出方案时，一维DP已经不够用了，因为你覆盖了之前行的状态。最简单的方法是在二维表算完后，从最后一个物品反向检查。

假设二维表dp已经算完，j从capacity开始，从i=n往i=1倒推。如果dp[i][j] == dp[i-1][j]，说明第i件物品没有被选；否则说明第i件物品被选了，把它的重量从j中减掉，继续往前推。

def knapsack_with_selection(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): w, v = weights[i - 1], values[i - 1] for j in range(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 - 1) j -= weights[i - 1] selected.reverse() return dp[n][capacity], selected

这里有一个容易踩的坑：如果存在多种最优方案，dp[i][j] == dp[i-1][j]和dp[i][j] == dp[i-1][j-w]+v可能同时成立，倒推时会选择“不选”那条路，导致最后输出的方案虽然最优，但没有包含某件同样可选的物品。这是回溯算法的固有特点之一，你只需要保证总价值正确即可，不要让“选了哪一条路径”这个问题影响对算法正确性的判断。

5.4 容易忽视的下标越界和重量为0问题

写背包时要确保dp[j-w]的下标满足j >= w。0-1背包模板中我用range(capacity, w-1, -1)直接避开越界；如果写成range(capacity, 0, -1)再在循环里加if j >= w，功能虽然一样，但多了一层判断。

真正危险的是重量为0的情况。当w=0时，dp[j]可以通过dp[j] + v自引用而累加，无论你正序还是倒序，语义都会变成“这件物品可无限次贡献价值”。所以在题目数据里看到重量为0，别急着套模板，先单独处理。更稳妥的做法是在读入数据时就将重量为0且价值大于0的物品单独累加到答案，或者直接过滤掉，以免污染DP数组。

6. 怎么识别一道新题是背包问题

6.1 三个特征帮你快速判断

面对一道新题，我一般先问自己三个问题：

1. 有没有一个明确的容量限制？这个限制可能是总重量、总预算、总时间、元素个数。
2. 有没有一组物品？每个物品对应一个或多个属性，如重量、成本、体积。
3. 目标是不是在限制内求某种极值，比如最大价值、最小数量、是否可达？

如果三个问题的答案都是“是”，那它大概率是背包问题的变体。比如“给定一个数组，问能否分成两个子集，使两个子集元素和相等”，表面看和背包没什么关系，但可以转换成：总数组和为sum，问能否找到一些元素，使它们的和恰好为sum/2。这就变成了“恰好装满的0-1背包”，容量是sum/2，物品是数组中每个数，重量和价值都是这个数本身，最后看dp[sum/2]是否可达。

6.2 最常见的几种变形套路

• 子集和问题：每个数只能用一次，判断能否凑出某个目标值。用布尔型DP，转移时做或运算。
• 分割等和子集：如上所述，变成子集和问题。
• 最少硬币数：完全背包基础上改求最小值，初始化为正无穷。
• 方案总数：DP数组存方案数，转移时做加法，而不是取max。
• 价值和容量互换：如果总重量很大但价值总和很小，可以把下标换成“当前总价值”，数组里存“达到该价值需要的最小容量”，最后扫描容量不超过限制的最大价值下标。

价值和容量互换是很多进阶题的精髓。比如某个物品的重量上限是10^9，但物品总价值最多只有10^5，如果坚持用重量做容量维度，二维数组直接爆炸；改成用价值做维度后，复杂度常常能救回来。这个技巧不是背来的，而是做题前先比较两组数量级：哪个维度小，就让哪个维度做DP下标。

6.3 什么时候不该用背包DP

背包DP不是万能的。如果物品数量很少，但容量巨大，比如n <= 20，那可以考虑折半搜索，甚至直接枚举子集；如果每件物品重量只有1和2两种，可以贪心；如果选择之间存在互斥关系，比如“选第i件就不能选第j件”，那可能要走树形DP或图上的思路；如果限制条件是两个以上互相独立的维度，就要加一维状态，也就是二维背包，复杂度会更高。

判断标准不是“题目里有没有背包两个字”，而是“状态能不能被有限个维度的笛卡尔积覆盖”。一旦状态空间超出内存或时间限制，就要往后退一步，寻找别的数学模型。

6.4 我个人的实战流程

我写代码和复习时有一套固定流程，分享给你。第一步，先读限制条件里的数据范围，判断n和容量的大小关系，决定是二维、一维，还是需要用价值做下标。第二步，写状态定义，用一句完整的话说清楚“dp是什么”，这句话必须包括所有影响决策的维度。第三步，写转移方程，先写文字版“不做什么/做什么”，再翻译成max/min/加/或。第四步，处理初始化，分清楚“不超过”还是“恰好”。第五步，写一个手算小样例，比如只有3件物品、容量5，亲自填表验证。

这套流程看起来笨，但最不容易出错。我见过太多人一上来就套模板，结果在循环方向或初始化上翻车，最后调试两小时也找不到原因。先花三分钟做手工表，其实是最快的调试方式。

写在最后的提醒

背包问题刷得再多，终究要落实到你能不能自己定义状态这件事上。我见过有人把0-1背包、完全背包的代码背得滚瓜烂熟，换个场景就懵了，因为只记住了循环方向，没记住为什么方向会改变。建议你学完这篇之后，自己把三种背包的二维转移方程各写一遍，再把一维优化的两种方向各跑一遍，用一个容量5左右的小例子验证输出。这个过程比看任何讲解都重要。我自己当初就是靠一支笔和一张纸把表格填通的，那份踏实感，是看再多视频都换不来的。