01背包和完全背包这两个名字我在带新人、自己刷题、以及帮同事复盘面试的时候讲过太多遍。绝大多数人第一次接触动态规划就是从这两道题开始的给一个容量有限的背包和一堆物品每件物品只能拿一次的叫01背包每种物品能反复拿的叫完全背包代码上往往只差一个循环方向结果却是两个完全不同的世界。这篇文章我打算把它讲透从为什么会有这两种背包一直讲到面试现场怎么一次写对、怎么排查写错的地方代码全部用Python给出可直接复制的版本。刚入门的新手可以顺着读做过几道题但总写错循环顺序的朋友建议重点看第三、四、七章那里是我认为最容易翻车的地方。1. 先把题目还原成真实的打包场景1.1 一个袋子到底能装多少你可以把自己想象成一个上门打包的师傅。面前摆着 N 件东西每件都有两个属性重量 w 和价值 v。你手上有一个承重上限为 V 的包目标只有一个——在不超过承重的前提下让装进去的东西总价值尽可能高。这就是背包问题最原始的样子跟算法、跟编程语言都没关系纯粹是一个资源分配的问题有限的容量怎么分给不同的物品收益最大。01背包和完全背包的区别只在于物品的库存。01背包里每件东西全世界只有一件你要么装进去要么留在原地不存在第二件完全背包里每种东西的库存是无限的只要包装得下你愿意塞几件就塞几件。这个差别听起来特别小很多人第一遍看题的时候甚至会忽略过去但恰恰是能不能重复取同一件物品这一点决定了状态转移方程里下标写 i 还是 i-1进而决定了滚动数组必须倒着遍历还是正着遍历。我见过太多人在面试里栽在这里题目明明是完全背包他按01背包的倒序写样例还能过一交评测就发现答案偏小反过来也一样01背包写成正序答案会偏大。所以别急着背代码模板先把这是哪一类判断清楚比什么都重要。1.2 为什么它被当成动态规划的第一课背包问题之所以经典是因为它把动态规划最核心的思想用最少的变量展示了出来把一个大问题拆成若干个相似的子问题把子问题的答案记下来避免重复计算。穷举所有组合的暴力做法复杂度是 2 的 N 次方N 到 20 左右就基本跑不动了而动态规划把它压到了 O(N × V)也就是说只要容量不是大到离谱一两千件物品、一两万容量都能秒出结果。这里面有个很关键的子结构假设我只看前 i 件物品并且把背包容量限定为 j那么这个状态下的最大价值只跟两个东西有关——前 i-1 件物品在容量 j 下的最优解以及前 i-1 件物品在容量 j-w[i] 下的最优解再加上当前物品的价值。换句话说大状态只依赖小状态而且依赖关系是有方向的、不会绕回自己。这就是能写递推、能用循环一层层推上去的前提。提示如果你对子问题这个词还没什么感觉可以记住一句话——动态规划就是把每一步都在做选择的过程变成每一步都记下最优答案的表格。背包的表格行是物品列是容量。1.3 三类问法先分清楚别上来就写代码同一个背包背景问法不同代码细节差别很大。我习惯先把它归到下面三类里再动手。问题类型典型问法关键差异求最大价值背包能装的最大价值是多少转移方程取 max容量不必装满求方案数有多少种装法 / 有多少种凑法转移方程做加法初始化 dp[0]1求可行性能不能恰好装满 / 能否凑出某个值布尔状态或 0/1 计数注意边界初始化判断类型之后再判断物品能不能重复取。这两步做完剩下的就是套模板和调初始化基本不会出大错。我个人习惯是在草稿纸上写下容量维度是 V 还是 V1、初始化 dp[0] 是 0 还是负无穷还是 1这三行先定下来代码就水到渠成了。2. 状态定义和转移方程是怎么想出来的2.1 dp[i][j] 到底代表什么先定状态这是所有动态规划的第一件事。在背包里我们定义 dp[i][j] 表示只考虑前 i 件物品在容量为 j 的前提下能拿到的最大总价值。注意这里的前 i 件是一个前缀不是一个任意子集这是保证子结构成立的关键容量为 j是容量上限不是恰好用满——这两点如果理解偏了后面的初始化就一定会错。定义完状态接着问自己一个问题dp[i][j] 是怎么从更小的状态走过来的答案只有两种可能。第一种第 i 件物品我不要那么答案就是前面 i-1 件物品在容量 j 下的最优解也就是 dp[i-1][j]。第二种第 i 件物品我要那么先给它腾出 w[i] 的空间剩下的空间留给前 i-1 件物品答案是 dp[i-1][j-w[i]] 再加上 v[i]。这两种情况取更大的那个就是转移方程。2.2 01背包的转移方程# 01背包二维写法 # dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])这里两个分支的下标都是 i-1因为01背包里每件物品只有一件拿了第 i 件之后第 i 件就不能再拿了所以剩下的空间必须交给前 i-1 件。这个 i-1 就是01背包的身份证看到它基本就能确定是01背包。还有一个必须处理的地方是边界当 j w[i] 的时候装不下只能走不选这一支不能硬算 j-w[i]否则下标会变成负数直接报错或者语义错乱。所以实际写代码的时候第二层循环的起点要从 w[i] 开始或者加一个 if 判断这两种写法等价我通常选前者省一次判断。2.3 完全背包的转移方程只改了一个下标完全背包的转移方程长这样# 完全背包二维写法 # dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])细心的朋友会发现第二个分支里写的是 dp[i][j-w[i]]不是 dp[i-1][j-w[i]]。这一个下标的区别就是全部秘密它表示腾出空间之后第 i 件物品还可以继续考虑也就是可以再拿一件、再拿一件一直拿到装不下为止。递推的过程中dp[i][j-w[i]] 内部已经包含了再拿第 i 件的可能性所以无限次取用被自动实现了不需要额外写一层循环去枚举拿几件。我特别喜欢用一句话总结这个差别01背包问的是这件东西我要不要拿一次完全背包问的是这件东西我还要不要再拿一件。前者是二选一后者是一个可以反复追问的过程而递推天然适合表达反复追问。2.4 二维状态的天生缺陷空间太大二维写法最好理解但空间是 (N1) × (V1)。当 N 是一千、V 是一万的时候就是一千万个整数Python 的 list 装这么多元素内存和速度都会很难看如果 V 到了几十万二维数组基本就崩了。所以真正的工程实现和比赛代码里我们几乎都用一维的滚动数组。理解二维是理解一维的必经之路但正式写的时候没必要坚持二维。3. 滚动数组从二维压到一维的关键一步3.1 为什么能压成一行观察转移方程会发现 dp[i][j] 只依赖两样东西同一行的左边某个位置完全背包的情况以及上一行的某个位置01背包的情况。也就是说当我们从上往下按物品逐行推的时候第 i 行算完第 i-1 行就再也不会被用到了。既然如此何必把每一行都留着用一维数组 dp[j] 覆盖着写就够了。这里有个很重要的细节覆盖是有方向的。dp[j] 在更新之前存的是上一轮的值更新之后存的是这一轮的值。如果我们在更新 dp[j] 的时候需要用到上一轮的 dp[j-w[i]]那就必须保证那个位置还没被这一轮改过如果需要用到这一轮的 dp[j-w[i]]那就必须保证它已经被改过。前者要求倒序遍历后者要求正序遍历。这就是整个背包问题里最核心的一句话。3.2 01背包为什么必须倒着走我拿一组最简单的数据推一遍你就明白了。假设当前物品重量 w1、价值 v15容量上限 V5一维数组初始全是 0。如果我们正序遍历 j1,2,3,4,5j1 时 dp[1] 变成 15j2 时用 dp[1]15而 dp[1] 刚刚才被这一轮更新过等于 15于是 dp[2]30。你看同一件物品被拿了两次这就变成了完全背包的行为。对01背包来说这是典型的错误。如果我们倒序遍历 j5,4,3,2,1j5 时用 dp[4]15此时 dp[4] 还是上一轮的 0得到 15j4 时用 dp[3]15dp[3] 也还是上一轮的 0得到 15……一路下来每个位置都只贡献了一次这件物品dp 变成 [0,15,15,15,15,15]完全正确。遍历方向dp[j-w] 的取值来源含义适用倒序 j: V → w上一轮的值每件物品最多用一次01背包正序 j: w → V这一轮的值每件物品可用无限次完全背包记住这张表比背十遍代码都管用。我自己在面试时如果紧张就默念01倒着走、完全正着走念两遍手就稳了。3.3 一个容易忽略的前提物品循环必须在最外层上面讨论的倒序正序前提是先遍历物品再遍历容量。绝大多数求最大价值的问题都满足这个前提代码怎么排都不影响答案。但在求方案数的问题里这个顺序会直接改变答案的含义这一点我在第六章会专门展开因为它是从会写模板到能判断题型的分水岭。还有一个前提是固定容量维度、外层物品这个结构要和你定义的 dp 语义对得上。我见过有人把 dp 定义成容量为 j 时处理到第 i 件的最大价值然后外层写容量、内层写物品结果数组更新顺序和语义对不上怎么调都不对。状态定义和循环顺序是一体的定义的时候就要想清楚外层转什么。4. 一组数据手推到底两种背包的完整推演4.1 数据准备我用一组很小的数据把两种背包的过程都手推一遍。物品三件编号重量 w价值 v111522203330容量 V 5。先心算答案01背包最优是拿 2 号和 3 号重量刚好 5价值 50其他组合1345、1235、123 超重都更小完全背包因为 1 号物品每单位重量价值最高15/1全拿 1 号五件价值 75。4.2 01背包逐行推演初始 dp [0, 0, 0, 0, 0, 0]下标 0 到 5。处理物品 1w1, v15j 从 5 倒着到 1j比较dp[j] 更新后5max(0, dp[4]1515)154max(0, dp[3]1515)153max(0, dp[2]1515)152max(0, dp[1]1515)151max(0, dp[0]1515)15数组变成 [0, 15, 15, 15, 15, 15]。处理物品 2w2, v20j 从 5 倒着到 2j比较dp[j] 更新后5max(15, dp[3]2035)354max(15, dp[2]2035)353max(15, dp[1]2035)352max(15, dp[0]2020)20数组变成 [0, 15, 20, 35, 35, 35]。处理物品 3w3, v30j 从 5 倒着到 3j比较dp[j] 更新后5max(35, dp[2]3050)504max(35, dp[1]3045)453max(35, dp[0]3030)35最终数组 [0, 15, 20, 35, 45, 50]答案 dp[5] 50和心算一致。4.3 完全背包逐行推演初始 dp [0, 0, 0, 0, 0, 0]。处理物品 1w1, v15j 从 1 正着到 5每一项都是 dp[j] dp[j-1] 15得到 [0, 15, 30, 45, 60, 75]。这里能明显看到重复拿的痕迹dp[5] 已经是五件物品 1。处理物品 2w2, v20j 从 2 正着到 5j比较dp[j] 更新后2max(30, dp[0]2020)303max(45, dp[1]2035)454max(60, dp[2]2050)605max(75, dp[3]2065)75数组不变说明物品 2 拼不过物品 1。处理物品 3w3, v30j 从 3 正着到 5j比较dp[j] 更新后3max(45, dp[0]3030)454max(60, dp[1]3045)605max(75, dp[2]3060)75最终数组还是 [0, 15, 30, 45, 60, 75]答案 75正确。这组数据也顺便说明了一件事完全背包的答案不一定用满多种物品就是要挑性价比最高的那一种往死里塞这点直觉在做题时很有用。4.4 两种推演给人的共同启示把这两张表放在一起看你会发现01背包和完全背包的差别全在于更新 dp[j] 时dp[j-w] 是旧值还是新值。倒序保住了旧值所以每件只拿一次正序用上了新值所以可以反复拿。理解到这个层次之后你就不需要死记01倒序、完全正序了你可以在考场上现推。5. 可以直接抄走的Python模板5.1 01背包二维版用来验证思路def knapsack_01_2d(weights, values, capacity): n len(weights) # dp[i][j]前 i 件物品、容量 j 的最大价值 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): dp[i][j] dp[i - 1][j] # 不拿第 i 件 if j w: dp[i][j] max(dp[i][j], dp[i - 1][j - w] v) return dp[n][capacity]二维版的好处是所见即所得调试的时候直接把整张表打出来一眼就能看出哪里算错了。我建议每个人在学的时候都先写一遍二维版跑通之后再压成一维这个过程只需要花二十分钟但能省掉后面很多莫名其妙的错。5.2 01背包一维版正式使用def knapsack_01(weights, values, capacity): dp [0] * (capacity 1) for w, v in zip(weights, values): if w capacity: # 单件就超重直接跳过 continue for j in range(capacity, w - 1, -1): # 关键倒序 if dp[j - w] v dp[j]: dp[j] dp[j - w] v return dp[capacity]range(capacity, w - 1, -1)这个写法几乎出现在我写的每一道背包题里起点是 capacity终点是 w步长 -1正好保证 j - w 不会小于 0。用 if 取代 max 是一个小优化在 Python 里函数调用开销不小数据量大时能省一点时间。5.3 完全背包一维版def knapsack_complete(weights, values, capacity): dp [0] * (capacity 1) for w, v in zip(weights, values): if w capacity: continue for j in range(w, capacity 1): # 关键正序 if dp[j - w] v dp[j]: dp[j] dp[j - w] v return dp[capacity]两个函数的差别只有一行的 range 参数这也解释了为什么很多人抄代码的时候容易抄错——模板长得太像了。我的做法是在函数名和注释里把方向写清楚必要的时候把关键那行单独加一条注释别嫌啰嗦。5.4 读入输出的实用写法import sys def main(): data sys.stdin.read().split() idx 0 n, capacity int(data[idx]), int(data[idx 1]); idx 2 weights, values [], [] for _ in range(n): weights.append(int(data[idx])) values.append(int(data[idx 1])) idx 2 dp [0] * (capacity 1) for w, v in zip(weights, values): for j in range(capacity, w - 1, -1): val dp[j - w] v if val dp[j]: dp[j] val print(dp[capacity]) main()一次性读完所有输入再解析比一行行 input() 快很多这一点在输入规模上万的时候特别明显。这个技巧不算高深但确实是我从反复超时里总结出来的。注意内层循环里尽量不要做多余的事情比如每次循环都调用一次 max()、每次都判断 w j这些在十万级规模下会累积成明显的耗时差异。6. 五种常见变体别只会做原题6.1 至多容量和恰好装满初始化完全不同前面的模板都是不超过容量所以 dp 全初始化为 0意思是什么都不装也是合法方案价值为 0。但如果题目要求恰好装满背包那么除了容量 0 之外其他容量在没有物品时都是不可达的必须初始化为负无穷求最大值时。NEG float(-inf) dp [NEG] * (capacity 1) dp[0] 0 for w, v in zip(weights, values): for j in range(capacity, w - 1, -1): if dp[j - w] ! NEG: dp[j] max(dp[j], dp[j - w] v)这个初始化的道理其实很直白dp[0] 0 表示容量为 0 时恰好装满价值是 0这是一个真实可达的状态而容量为 5、一件物品都没有这种状态根本不存在所以标记为负无穷。数组推到后面负无穷会沿着不可达的路径一直传染下去凡是算出来还是负无穷的位置就是无法恰好装满的容量。这个细节在分割等和子集目标和这类题里反复出现忘记改初始化几乎必错。6.2 求方案数外层放物品还是放容量结果完全不同这是我个人认为最容易掉进去的一个坑。同样是完全背包求方案数外层循环放物品还是放容量得到的答案含义不一样。# 写法A外层物品内层容量组合数不看顺序 def count_combinations(coins, target): dp [0] * (target 1) dp[0] 1 for c in coins: for j in range(c, target 1): dp[j] dp[j - c] return dp[target] # 写法B外层容量内层物品排列数看顺序 def count_permutations(coins, target): dp [0] * (target 1) dp[0] 1 for j in range(1, target 1): for c in coins: if j c: dp[j] dp[j - c] return dp[target]用硬币 [1, 2] 凑 3 来验证组合数答案是 2111 和 12排列数答案是 3111、12、21。为什么会有这个差别写法A里每种硬币作为一个整体被一次性考虑进去一旦处理完硬币 1后面的递推不会再回到再拿一枚硬币 1 并放在硬币 2 后面这种顺序所以天然去重写法B是按金额从小到大推每一步都可以从任意硬币转移过来自然会区分先后顺序。判断方法很简单题目问有多少种组合方式有多少种凑法用写法A题目问有多少种走法有多少种排列用写法B。我当年在这上面栽过一次题目是零钱兑换的方案数我用了写法B样例刚好只有一个答案直到提交才被打回来。6.3 多重背包和分组背包的快速判别除了01和完全还有两个经常混进来的变体。多重背包是每种物品有有限个比如 3 个做法常见的是二进制拆分把3 个拆成1 个 2 个拆出来的每一份当成01背包里的独立物品分组背包是每组里最多选一件做法是先遍历组组内遍历容量然后组内遍历该组的所有物品保证一组只被选一次。判别方法我总结了三个问题库存是 1、无限还是有限同一组内是否互斥有没有至少选一件必须选满 k 件这类附加条件。三个问题答完类型基本就锁定了。多重背包的二进制拆分是个很漂亮的技巧但说实话能把它讲清楚的前提是先彻底理解01背包所以别急着跳。6.4 几个换皮题认出来就不难分割等和子集判断能不能凑出总和的一半本质是01背包的可行性版本dp 是布尔数组。目标和给一堆数加正负号让结果等于目标值本质是01背包求方案数。零钱兑换凑出目标金额所需的最少硬币数完全背包求最小值初始化要设成一个大数。爬楼梯进阶版一步可以上 1 到 k 级台阶本质是完全背包求排列数。这些题之所以让人发懵是因为题干里根本没有背包两个字。我自己的习惯是看到从一堆东西里选有容量或上限约束求最大/最少/多少种就自动往背包上靠然后再判断01还是完全、求值还是求方案数。7. 常见问题与排查技巧实录7.1 一图流排查表现象最可能的原因处理方式答案偏大出现明显重复计数01背包写成了正序内层改成倒序答案偏小凑不出多次取用完全背包写成了倒序内层改成正序恰好装满类题目结果全是负无穷初始化没改成负无穷dp[0]0其余设为负无穷方案数答案偏多排列数写成了组合数或反之检查外层循环是物品还是容量单件重量大于容量时报错没做 w capacity 的判断循环前先跳过或限制起点数据量大时超时用了 input() 逐行读 / 内层调用 max改用 sys.stdin.read() 和 if 比较内存爆掉用了二维数组压成一维滚动数组这张表我建议直接抄进自己的笔记里遇到问题先对着看一遍通常三十秒内就能定位。7.2 我踩过的四个坑第一个坑是想当然地认为样例过了就对了。背包题的错误往往在数据规模变大之后才暴露特别是01背包写成正序这种情况小容量、单件物品的样例完全看不出问题。后来我养成了一个习惯写完代码之后自己构造一组同一件物品价值特别高的数据单独测一遍如果它在结果里出现了两次以上就说明循环方向错了。第二个坑是容量维度开小了。dp 数组的长度必须是 capacity 1因为要表示从 0 到 capacity 的所有容量。我有一回写成了 capacity结果每次读到最大容量时都越界报的错还特别隐晦最后打了半天的日志才发现。现在我在写这两行的时候会下意识数一遍括号里的加号。第三个坑是忽略物品顺序无所谓这件事。求最大值时物品谁先谁后不影响结果但对拍的时候我曾经用同一组数据的两种顺序去验证发现输出不一样白白折腾了半小时最后发现是我第一版代码里有一处正序倒序混写。对拍是个好习惯但前提是你的两份代码都写对了。第四个坑是在求方案数时把初始化写成 dp [1] * (n1)。这种写法看起来每个容量都至少有一种方案但实际上是错的会导致所有位置都多算。正确做法是 dp[0] 1其余为 0含义是凑出金额 0 有一种方案什么都不选。这个1的含义很多人没想明白就开始套模板。提示面试的时候如果你不确定循环方向可以主动跟面试官说我这里想先确认一下物品能不能重复使用这既是澄清题意也是展示你理解了两者的本质区别。7.3 复杂度和数据规模对照解法时间复杂度空间复杂度适用规模参考暴力枚举O(2^N)O(N)N ≤ 20二维动态规划O(N × V)O(N × V)N、V 均 ≤ 1000一维滚动数组O(N × V)O(V)N ≤ 2000V ≤ 5 万一维 提前剪枝接近 O(N × V)O(V)存在大量超重物品时更快容量特别大比如上百万而物品很少时背包就不太适合了那时候要考虑别的思路比如按价值维度做状态、或者用折半查找。这个边界判断不是靠背是靠对复杂度的直觉——看到 N 很小、V 很大就该警惕了。我把这套东西完整写了一遍其实最想说的是01背包和完全背包的区别不在代码长度而在你对状态从哪里来的理解深度。倒序和正序这两行看似是记忆负担一旦用推演的方式理解透了它们反而会变成你判断题型最可靠的依据。做题的时候别怕画表格手推一组七八个格子的小数据比盯着代码看十分钟都有效。