背包问题Knapsack Problem是动态规划里最有代表性的一类模型01背包、完全背包、多重背包、分组背包这四个变种几乎撑起了容量加选择这个套路的全部骨架。我带过不少刚接触动态规划的朋友也见过太多人把01背包写得滚瓜烂熟转头在完全背包上把容量循环方向写反跑出来的答案偏偏还看着像对的最后自己都找不出问题在哪。这篇不打算只丢几个模板给你背而是把每一条转移方程背后真正在发生的事情讲清楚从状态定义、循环嵌套顺序一直到初始化边界和方案数统计一个环节一个环节拆开。不管你是刚开始刷算法题还是准备面试前把动态规划这块补扎实都可以顺着往下看中间我会塞几个自己踩过的坑都是文档里不会写的。1. 先想清楚四类背包到底在解决什么模型背包问题的通用描述其实一句话就能说完有一个容量为 C 的背包还有 n 个物品每个物品有自己的重量 w[i] 和价值 v[i]要求在总重量不超过 C 的前提下挑出一部分物品让总价值尽可能大。听起来很朴素但它抽象的是有限资源下做取舍这件事——预算怎么分配、时间怎么安排、集装箱怎么装箱本质上都能往这个框里套。也正因为抽象层次高它才成了动态规划入门绕不开的一道坎。1.1 统一的问题框架把这四类背包放在一张桌子上看它们共享同一套符号容量 C、物品数量 n、第 i 件物品的重量 w[i] 和价值 v[i]。区别只在于每件物品能拿几次这个约束上。我习惯先把这个约束画出来再去写状态转移因为约束一变循环的写法就跟着变硬背模板特别容易串味。01背包每件物品最多拿一次拿了就是拿了不能重复。完全背包每件物品可以拿无限次只要背包塞得下。多重背包每件物品有数量上限 s[i]拿的数量在 0 到 s[i] 之间。分组背包物品被分成若干组每组里最多只能挑一件出来。很多人第一次学的时候觉得这是四个完全不同的东西得各记一套代码。其实不是。它们的状态定义可以完全共用差异全部集中在内层循环怎么写。等你把这点想通四份代码在你脑子里会自动合并成一份。1.2 变种的差异只体现在三个位置我总结过一个判断方法遇到任何一个背包变种先问自己三个问题答案基本就把代码定死了。第一个问题状态怎么定义。绝大多数情况下dp[j] 表示容量为 j 时能拿到的最大价值。这个定义四类背包通用不需要改。第二个问题容量这一维是正序还是倒序。这一条区分了01背包和完全背包。01背包倒序完全背包正序原因后面会用一整节讲透这里先记住结论。第三个问题循环的嵌套层次谁在外、谁在内。01背包和完全背包是物品在外、容量在内分组背包必须在最外层加一层组然后在组内部处理容量和物品。多重背包稍微特殊它要在物品层面做拆分把数量上限这个约束消化掉再退化成01背包。这三个问题的答案一旦确定剩下的就是往里填公式。我见过太多人跳过这一步直接抄代码结果题目稍微一变形就懵了——比如把求最大价值改成求方案数或者加上恰好装满的限制模板立刻不够用。所以别急着背先把这三个位置搞明白。2. 状态定义与遍历顺序把模板背后的原理讲透这一节是全文的核心。如果你只想记住一个结论那就是背包问题里最容易出错、也最能体现理解深度的不是转移方程本身而是遍历顺序。方程短得能背下来顺序错了却很难肉眼发现因为错误的代码往往也能跑出数只是数是错的。2.1 dp数组的滚动结构先从二维说起。最朴素的想法是开一个二维数组 dp[i][j]表示只考虑前 i 件物品、容量为 j 时的最大价值。转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])它的含义很直白对于第 i 件物品要么不选继承 dp[i-1][j]要么选腾出 w[i] 的容量加上 v[i] 的价值。两种取最大。但二维数组在物品多、容量大的时候特别吃内存。观察一下就能发现计算第 i 行只依赖第 i-1 行再往前的行压根用不上。于是可以把它压成一维数组 dp[j]边算边覆盖。这个技巧叫滚动数组是背包问题从能写到写得好的关键一步。压成一维之后方程变成dp[j] max(dp[j], dp[j - w[i]] v[i])注意这时候 dp[j - w[i]] 到底代表上一轮还是本轮的值就变得极其关键了。等号右边的 dp[j] 是旧值dp[j - w[i]] 是不是旧值取决于你怎么遍历 j。2.2 01背包为什么容量必须倒序我们拿一个具体的例子把这件事推一遍。假设背包容量 C5物品只有一件w2v3。正序遍历容量会怎样初始 dp [0,0,0,0,0,0]下标 0 到 5。正序遍历 j 从 2 到 5j2dp[2] max(dp[2], dp[0]3) 3j3dp[3] max(dp[3], dp[1]3) 3j4dp[4] max(dp[4], dp[2]3) 33 6j5dp[5] max(dp[5], dp[3]3) 33 6问题出在 j4 这一步。dp[2] 在 j2 的时候已经被更新成 3 了也就是说算 dp[4] 时用到的 dp[2] 是本轮刚算出来的值相当于物品被用了两次。这恰恰是完全背包的语义不是01背包。倒序遍历就没事。j 从 5 降到 2j5dp[5] max(0, dp[3]3) 3dp[3] 还是旧值 0j4dp[4] max(0, dp[2]3) 3dp[2] 还是旧值 0j3dp[3] max(0, dp[1]3) 3j2dp[2] max(0, dp[0]3) 3每一步引用到的 dp[j-w[i]] 都是下标更小、还没被本轮碰过的位置所以拿到的一定是上一轮的旧值等价于二维数组里的 dp[i-1]。这就是01背包倒序的本质。注意判断正序倒序的时候不要死记而是问自己一句——算 dp[j] 时需要用到的那个 dp[j-w[i]]在这一轮里有没有被提前改过会被改就倒序需要它被改重复用物品就正序。2.3 完全背包正序的来历既然01背包倒序是为了避免重复使用那完全背包要的就是重复使用所以直接正序。逻辑上完全自洽。再拿刚才那个例子推一遍现在把它当完全背包处理物品 w2v3容量 5可以无限拿j2dp[2] max(0, dp[0]3) 3j3dp[3] max(0, dp[1]3) 3j4dp[4] max(0, dp[2]3) 33 6dp[2] 是本轮值相当于又拿了一个j5dp[5] max(0, dp[3]3) 33 6dp[5]6意味着装两个物品每个重2共重4还剩1的容量空着价值 336。这符合无限拿的语义。所以两段代码的文字差别只有那个range的方向语义差别却是用一次和用无数次。3. 四类背包的代码落地与手推验证光讲原理不够下面把四份代码都写出来每份配一段手推过程方便你对着验证。语言统一用 Python逻辑在其他语言里完全一样。3.1 01背包从二维到一维的滚动数组def knapsack_01(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): w, v weights[i], values[i] # 容量倒序保证每件物品只用一次 for j in range(capacity, w - 1, -1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity]拿一组数据手推w [2, 3, 4]v [3, 4, 5]容量 C 5。处理第一件 (2,3)容量从 5 降到 2dp 变成[0,0,3,3,3,3]。处理第二件 (3,4)容量从 5 降到 3dp 变成[0,0,3,4,4,7]。处理第三件 (4,5)容量从 5 降到 4dp 变成[0,0,3,4,5,7]。最终 dp[5]7对应选第一件和第二件重量 235价值 347结果对得上。这里有个容易忽略的细节内层循环的终点是w - 1也就是range的第二个参数写 w-1因为容量小于 w 时根本放不下这件物品循环也没必要跑。写成range(capacity, w-1, -1)是固定套路数字别写错。3.2 完全背包一行代码之差def knapsack_complete(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): w, v weights[i], values[i] # 容量正序允许同一物品被反复使用 for j in range(w, capacity 1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity]跟01背包唯一的不同就是内层循环方向反过来。这行代码看着简单但它是无数人第一遍学动态规划时翻车的地方——因为两个函数长得太像复制过来改个名字忘了改方向代码照样跑结果就是错的。手推一组w [2, 3]v [3, 4]容量 5每件无限拿。处理 (2,3) 后 dp [0,0,3,3,6,6]处理 (3,4) 后 dp [0,0,3,4,6,7]。最终 dp[5]7对应拿一件 (2,3) 和一件 (3,4)重量 5价值 7。如果换成拿两个 (2,3)重量 4价值才 6不如 7 大所以 7 是正确答案。3.3 多重背包二进制拆分与单调队列优化多重背包多了数量上限 s[i]最笨的做法是把每件物品复制 s[i] 份直接当01背包跑。这个方法正确但慢复杂度是 O(n·C·s)s 一大就炸。二进制拆分的思路是把数量拆成若干个打包好的物品。比如某物品有 3 件拆成 1 件和 2 件两部分有 8 件拆成 1、2、4、1 四部分。为什么这样拆因为任意一个 0 到 s 之间的数量都能用这些拆出来的份数组合表示。这不是巧合它跟二进制表示数的方式是同一个数学原理把 s 写成二进制各个位的和就能覆盖它以下的全部整数。def knapsack_multiple(weights, values, counts, capacity): dp [0] * (capacity 1) items [] for i in range(len(weights)): k 1 s counts[i] while k s: items.append((weights[i] * k, values[i] * k)) s - k k 1 if s 0: items.append((weights[i] * s, values[i] * s)) # 拆完之后就是标准01背包 for w, v in items: for j in range(capacity, w - 1, -1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity]拆分把复杂度降到 O(n·C·log s)这个量级基本够用了。但如果题目卡得很死还有更狠的做法单调队列优化复杂度能压到 O(n·C)。它利用的是按容量对 w 取模分余数每一类余数上的转移是一个滑动窗口取最大值的问题用单调队列维护窗口均摊每条是 O(1)。这个写法偏进阶实现时容易因为原地更新污染上一轮的值而出错稳妥的做法是另开一个数组承接本轮结果from collections import deque def knapsack_multiple_monotonic(weights, values, counts, capacity): dp [0] * (capacity 1) for i in range(len(weights)): w, v, c weights[i], values[i], counts[i] new_dp dp[:] for r in range(w): q deque() for m in range(0, (capacity - r) // w 1): j r m * w val dp[j] - m * v while q and q[-1][1] val: q.pop() q.append((m, val)) while q and q[0][0] m - c: q.popleft() new_dp[j] q[0][1] m * v dp new_dp return dp[capacity]提示单调队列优化在面试里很少要求手写能把二进制拆分写对、说出单调队列的思路基本就够用了。别为了炫技在时间紧张的场景硬上写错了反而扣分。3.4 分组背包循环嵌套顺序是成败关键分组背包的约束是每组最多选一件。这个约束决定了它的循环结构必须这样写最外层枚举组中间层倒序枚举容量最内层枚举组内的物品。def knapsack_group(groups, capacity): # groups: [[(w, v), (w, v)], ...] dp [0] * (capacity 1) for group in groups: for j in range(capacity, -1, -1): for w, v in group: if j w: dp[j] max(dp[j], dp[j - w] v) return dp[capacity]为什么容量和物品的层次不能调换如果让物品在外、容量在内那么在处理同一组时容量从小到大扫就可能出现这一组里选了两件的情况违反了约束。把容量放外层、并倒序等价于每组只做一次整体决策组内物品之间天然互斥。手推一组group1 [(2,3), (3,4)]group2 [(4,5)]容量 5。处理 group1 后 dp [0,0,3,4,4,4]处理 group2 后 dp [0,0,3,4,5,5]。dp[5]5对应选 group2 的 (4,5)。如果选 group1 的 (3,4) 再想加 group2 的 (4,5)重量 7 超了所以 5 是最优。结果合理。4. 方案数、路径还原与状态变形模板题会做了接下来是会变形。面试和比赛里最常出现的两种变形是求方案数和恰好装满另外还有输出具体选了哪些物品。4.1 求方案数把 max 换成求和如果题目问的是有多少种选法能达到目标容量转移方程里的 max 要换成加法。以01背包方案数为例def count_ways_01(weights, capacity): dp [0] * (capacity 1) dp[0] 1 for w in weights: for j in range(capacity, w - 1, -1): dp[j] dp[j - w] return dp[capacity]这里 dp[0]1 表示不选任何物品也是一种方案是递推的起点这个 1 千万不能漏。完全背包求方案数就把方向换成正序其余不变。有个细节值得强调求方案数和求最值的遍历方向规则是完全一致的。01背包求方案数依然倒序完全背包依然正序。原因是同一个——倒序保证物品只用一次正序允许重复。所以别把求方案数单独当成一个新知识点背它就是原方程换个运算符号。4.2 恰好装满与至多装的初始化差异这是背包问题里最容易被忽略、又最常出错的边界。初始化的方式取决于题目要求的是恰好装满容量 C还是容量不超过 C 就行。目标dp[0]其他位置含义恰好装满0-无穷大只有容量0是合法起点至多装默认00空背包也是合法状态为什么要这么设对于恰好装满dp[j] 必须表示容量 j 被正好填满时的价值。容量 0 天然是装满的所以 dp[0]0而容量 j 一开始不可能被填满就设成负无穷让它在转移里被淘汰掉。对于至多装任何容量下空着都是允许的所以全部初始化为 0。如果你把恰好装满的 dp 全设成 0代码不报错但答案会偏大因为它把没装满的状态也当成合法的了。这个坑我踩过不止一次特别是在做那种把数组里若干个数凑成目标和的题时。4.3 输出具体方案与字典序最小有些题不光要最大价值还要你输出选了哪些物品。常见做法是保留二维 dp然后从 dp[n][C] 往回倒推如果 dp[i][j] ! dp[i-1][j]说明第 i 件物品被选了于是记录它、把 j 减去 w[i]、i 减 1否则直接 i 减 1。如果题目要求字典序最小通常指选择的物品编号序列字典序最小倒推的起点和方向要注意更稳妥的方式是从前往后决策在贪心地能选就选时保证字典序。具体细节随题目而定核心是先保证 dp 计算正确再去回溯。5. 常见问题与排查技巧实录这一节是我这些年debug攒下来的经验基本都是代码能跑但答案不对的典型场景。5.1 遍历顺序写反的症状与验证方法01背包和完全背包写反是最常见的一类错误。怎么快速定位给你一个自检方法构造一个只有一件物品、容量刚好能装下两份它的情况。比如 w2、v3、C4。如果是01背包答案应该是 3只能拿一件如果跑出来 6说明你拿了两件顺序写反了。用这种最小反例去验证比盯着代码看快得多。分组背包的层次写反症状是答案里出现了同一组的两件物品一般出现在组内物品数量大于 1、且总价值恰好大于单件的时候。同样可以构造最小反例定位。5.2 初始化踩过的三个坑第一个坑是漏了 dp[0]1求方案数时答案永远是 0 或者偏小。第二个坑是把恰好装满的 dp 全初始化成 0答案偏大。第三个坑是求方案数时忘记考虑取模题目要求对一个大质数取余你没取中间结果直接溢出或者被 Python 的大整数拖慢。这三个坑有个共同点都不会让程序崩溃只会让你得到一个看起来像对的错误答案。所以在提交前习惯性地检查一遍初始化和取模能省下很多返工时间。5.3 多维与超大容量场景的处理背包问题还有几个方向值得留意。一是多维背包比如同时限制重量和体积这时 dp 变成二维循环嵌套再加一层原理不变。二是超大容量容量到 10^9 级别时线性容量的做法直接废掉需要考虑折半枚举或者别的思路。三是物品数量巨大时优先考虑单调队列优化而不是二进制拆分。注意遇到新变种先判断它属于四类里的哪一类再看容量维度是否要加最后确认遍历方向。这套判断流程比背模板稳得多。6. 刷题与实战中的一些个人体会最后聊点方法论。我自己学背包问题最大的转折点是意识到这四类其实是一类。在这之前我把它们当成四个互不相关的题去刷刷完就忘。后来我把状态定义、遍历方向、循环层次这三个变量画成一张表每遇到一道新题就先往表里填填完再写代码效率立刻不一样了。我的具体建议是先把01背包和完全背包的二维、一维写法各手推三遍直到能闭着眼解释每一步为什么这么算再拿多重背包练二进制拆分理解为什么任意数量都能被拆出来的份数组合覆盖最后用分组背包收尾重点体会循环层次的约束作用。整个流程走下来再回头去看那些变形题比如求方案数、恰好装满、输出路径你会发现它们都只是在这套骨架上换个零件而已。真要说有什么捷径就是别怕手推。代码跑一遍得到答案很快但只有自己拿纸笔把 dp 数组一个格子一个格子填过去才知道哪一步在用旧值、哪一步在用新值。动态规划这东西脑子里过一遍和手上过一遍效果差得不是一点半点。