1. 为什么0/1背包值得反复拿出来讲0/1背包问题在算法学习里的地位有点像学吉他时的爬格子——看起来简单但真正能把它吃透的人并不多。我见过不少朋友LeetCode上刷了几十道动态规划的题回头再写0/1背包还是会在遍历顺序、状态定义、边界初始化这些地方翻车。原因很简单大多数人只记住了“倒序遍历”这个结论却没搞清楚它为什么必须倒序更没搞明白从暴力递归到记忆化搜索再到递推DP每一步到底在优化什么。这篇文章就是要把这条演进路线完整地拆开。我会从最朴素的暴力递归写起一步步推到记忆化搜索再推到二维数组的递推DP最后压缩成一维数组。每一版代码我都会解释清楚它的状态定义、转移逻辑、时间复杂度和空间复杂度以及为什么下一版能比上一版更优。适合的读者是已经学过递归和基础DP但总觉得0/1背包理解得不够透彻想彻底搞明白每一个细节的人。如果你正在准备面试或者想给动态规划打个扎实的地基这篇内容应该能帮到你。核心关键词0/1背包、暴力递归、动态规划。这三个词基本就是这篇文章的主线我会沿着这条线一路推下去。2. 问题定义与暴力递归的起点2.1 0/1背包到底在问什么先把问题说清楚。你有一个容量为C的背包面前摆着n件物品第i件物品的重量是w[i]价值是v[i]。每件物品你只有两种选择要么整个装进背包要么不装。不能装一半也不能装多次。目标是在不超过背包容量的前提下让装进背包的物品总价值最大。“0/1”这个名字就是这么来的——每件物品的选择只有0不拿和1拿两种状态。这个约束看起来简单但它直接决定了问题的难度你不能像分数背包那样按性价比贪心因为拿了性价比最高的那件可能就装不下另外两件加起来更值钱的了。举个具体例子。背包容量C 10物品如下物品编号重量 w价值 v035146257368如果贪心地按性价比价值/重量排序物品0性价比1.67最高先拿物品0剩余容量7再拿物品1剩余容量3物品2和3都装不下。总价值11。但最优解其实是拿物品1和物品3重量4610价值6814。这就是0/1背包不能用贪心的经典反例。2.2 暴力递归最直白的“选或不选”面对“每件物品选或不选”这个问题最自然的想法就是递归穷举。定义函数dfs(i, cap)表示从第i件物品开始考虑当前背包剩余容量为cap时能获得的最大价值。转移逻辑很直接如果i n没有物品可考虑了返回0。如果w[i] cap这件物品装不下只能跳过返回dfs(i1, cap)。否则取两种选择的最大值不拿这件物品是dfs(i1, cap)拿这件物品是v[i] dfs(i1, cap - w[i])。def knapsack_brute(w, v, C): n len(w) def dfs(i, cap): if i n: return 0 if w[i] cap: return dfs(i 1, cap) return max(dfs(i 1, cap), v[i] dfs(i 1, cap - w[i])) return dfs(0, C)这段代码逻辑上完全正确但时间复杂度是O(2^n)。为什么因为每件物品都有两个分支递归树是一棵满二叉树叶子节点数量是2^n。当n 30的时候2^30大约是10亿次调用跑起来基本就卡死了。我实测过n 25左右纯Python的暴力递归大概要跑几秒钟n 30就要几十秒甚至更久。所以暴力递归只能用来理解问题结构不能作为最终方案。注意写暴力递归的时候一定要先写清楚“状态是什么”和“选择是什么”。状态是(i, cap)选择是“拿”或“不拿”。这两个东西定义清楚了后面的优化才有方向。2.3 暴力递归里藏着的重复计算暴力递归慢根本原因是大量重复子问题被反复计算。还是用上面那个例子dfs(2, 7)这个状态可能从多条路径到达先拿物品0再拿物品1或者先拿物品1再拿物品0都会走到“考虑物品2、剩余容量7”这个状态。每到达一次就重新算一遍浪费了大量时间。你可以把递归树画出来会发现同一层的很多节点状态是完全一样的。状态总数其实只有n × (C1)个但暴力递归算了2^n次。这就是优化的切入点把算过的状态存起来下次直接查表。3. 记忆化搜索给递归加一本备忘录3.1 记忆化的核心思路记忆化搜索Memoization的思路非常朴素既然同一个状态会被重复计算那我第一次算出来之后把它记下来下次再遇到直接返回。用一个二维数组memo[i][cap]来存dfs(i, cap)的结果初始值设为-1表示“还没算过”。def knapsack_memo(w, v, C): n len(w) memo [[-1] * (C 1) for _ in range(n 1)] def dfs(i, cap): if i n: return 0 if memo[i][cap] ! -1: return memo[i][cap] if w[i] cap: res dfs(i 1, cap) else: res max(dfs(i 1, cap), v[i] dfs(i 1, cap - w[i])) memo[i][cap] res return res return dfs(0, C)加了备忘录之后每个状态(i, cap)最多被计算一次。状态总数是n × (C1)每个状态的转移是O(1)所以时间复杂度降到O(nC)。空间复杂度也是O(nC)因为要开一个二维数组存所有状态。3.2 记忆化搜索的边界与初始化细节这里有几个容易踩的坑我一个个说。第一个坑是memo的初始值。如果所有物品的价值都是正数那用-1标记“未计算”是安全的因为合法结果不可能是负数。但如果题目允许价值为0甚至为负-1就可能和合法结果冲突。更稳妥的做法是用一个单独的visited数组或者把memo初始化成None。第二个坑是memo的维度。i的取值范围是0到n所以第一维要开n1cap的取值范围是0到C所以第二维要开C1。我见过有人开成n × C结果i n的时候越界。第三个坑是递归深度。当n很大的时候Python默认的递归深度限制通常是1000可能会被触发。如果n超过900建议改成递推写法或者手动调高递归深度限制。实操心得记忆化搜索是从暴力递归到递推DP的最佳过渡。它的代码结构和暴力递归几乎一样只是多了“查表”和“写表”两步。如果你对递推DP的遍历顺序总是搞不清楚不妨先用记忆化搜索把问题跑通再对照着改成递推。3.3 记忆化搜索和递推DP的关系记忆化搜索是“自顶向下”的从dfs(0, C)出发遇到没算过的状态就递归下去算算完存起来。递推DP是“自底向上”的从最小的子问题开始一层一层往上填表。两者本质上算的是同一张表只是填表顺序不同。记忆化搜索的优点是代码直观、不用考虑遍历顺序缺点是递归有函数调用开销而且可能爆栈。递推DP的优点是快、没有递归开销缺点是需要想清楚遍历顺序尤其是压缩空间之后顺序错了结果就错了。4. 二维递推DP把递归树摊平成一张表4.1 状态定义与转移方程把记忆化搜索改成递推第一步是明确dp数组的含义。定义dp[i][cap]为从前i件物品也就是物品0到i-1中选背包容量为cap时能获得的最大价值。注意这里的i表示“考虑前i件”而不是“从第i件开始”。这两种定义方式都可以但对应的转移方程和初始化不一样。我习惯用“前i件”这种定义因为它和递推的填表顺序更契合。转移方程如果不选第i件物品注意这里的第i件对应下标i-1dp[i][cap] dp[i-1][cap]如果选第i件物品前提是cap w[i-1]dp[i][cap] dp[i-1][cap - w[i-1]] v[i-1]取两者最大值。用公式写出来就是dp[i][cap] dp[i-1][cap] if w[i-1] cap dp[i][cap] max(dp[i-1][cap], dp[i-1][cap-w[i-1]] v[i-1]) if w[i-1] cap4.2 初始化与遍历顺序初始化dp[0][cap] 0表示前0件物品也就是没有物品能获得的最大价值是0。这个初始化很自然但很多人会忽略它的重要性。dp[0][*]是整张表的“地基”后面所有的值都是从这一行推出来的。遍历顺序外层循环i从1到n内层循环cap从0到C。为什么cap要从小到大因为dp[i][cap]依赖的是dp[i-1][cap]和dp[i-1][cap-w[i-1]]这两个都在上一行和本行的遍历顺序无关。所以从小到大、从大到小都可以。但为了和后面一维压缩的写法保持一致建议养成从小到大的习惯。def knapsack_2d(w, v, C): n len(w) dp [[0] * (C 1) for _ in range(n 1)] for i in range(1, n 1): for cap in range(C 1): if w[i-1] cap: dp[i][cap] dp[i-1][cap] else: dp[i][cap] max(dp[i-1][cap], dp[i-1][cap - w[i-1]] v[i-1]) return dp[n][C]时间复杂度O(nC)空间复杂度O(nC)。和记忆化搜索一样但没有了递归开销实际跑起来会快不少。4.3 手动模拟一遍填表过程还是用前面的例子C 10物品为(3,5), (4,6), (5,7), (6,8)。我来手动填几行帮你建立直觉。dp[0][*]全是0。考虑物品0重量3价值5dp[1][cap]cap 3装不下dp[1][cap] dp[0][cap] 0cap 3dp[1][cap] max(0, 05) 5所以dp[1] [0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 5]。考虑物品1重量4价值6dp[2][cap]cap 4dp[2][cap] dp[1][cap]cap 4dp[2][cap] max(dp[1][cap], dp[1][cap-4] 6)比如cap 7dp[1][7] 5dp[1][3] 6 5 6 11取11。这表示容量7时拿物品0和物品1总价值11比只拿物品0的5更优。继续填下去最后dp[4][10]就是答案。你可以自己动手填一遍填完之后对动态规划的理解会深很多。提示手动模拟是理解DP最有效的方法没有之一。看十遍代码不如自己填一遍表。填表的时候重点关注“当前格子的值是从哪几个格子推出来的”这样你就能直观地看到状态转移的路径。5. 一维数组压缩把空间砍掉一个维度5.1 为什么可以压缩观察二维DP的转移方程dp[i][cap]只依赖dp[i-1][*]也就是只依赖上一行。这意味着我们不需要保存整张表只需要保存上一行的数据就够了。更进一步我们可以直接在原地更新一个一维数组。定义dp[cap]为当前考虑的物品范围内容量为cap时能获得的最大价值。当我们处理第i件物品时dp[cap]在更新前代表的是“前i-1件物品”的结果更新后代表“前i件物品”的结果。转移方程变成dp[cap] max(dp[cap], dp[cap - w[i-1]] v[i-1])5.2 为什么内层循环必须倒序这是0/1背包最核心、也最容易搞错的一个点。一维压缩之后内层循环cap必须从C倒序遍历到w[i-1]。为什么假设我们正序遍历。当处理到cap时dp[cap - w[i-1]]已经被本轮的更新覆盖过了它代表的是“已经考虑过第i件物品”的结果。那么dp[cap] dp[cap - w[i-1]] v[i-1]就相当于在第i件物品已经被选了一次的基础上又选了一次这就变成了完全背包问题而不是0/1背包。倒序遍历的时候dp[cap - w[i-1]]还没有被本轮更新它仍然是“前i-1件物品”的结果。这样转移才是正确的。用一个具体数字来验证。假设物品0重量3价值5C 5。初始dp [0,0,0,0,0,0]。正序遍历cap 3dp[3] max(dp[3], dp[0]5) 5cap 4dp[4] max(dp[4], dp[1]5) 5cap 5dp[5] max(dp[5], dp[2]5) 5看起来没问题因为只有一个物品。但如果有两个物品正序就会出问题。假设再加物品1重量3价值6正序遍历cap 3dp[3] max(5, dp[0]6) 6cap 4dp[4] max(5, dp[1]6) 6cap 5dp[5] max(5, dp[2]6) 6cap 6dp[6] max(0, dp[3]6) 66 12dp[6] 12意味着物品1被拿了两次dp[3]已经是拿了物品1的结果再加物品1的价值。但0/1背包里物品1只能拿一次正确结果应该是max(拿物品0物品111, 只拿物品16) 11。倒序遍历cap 6dp[6] max(0, dp[3]6) 56 11cap 5dp[5] max(5, dp[2]6) 5cap 4dp[4] max(5, dp[1]6) 5cap 3dp[3] max(5, dp[0]6) 6最终dp[6] 11正确。def knapsack_1d(w, v, C): n len(w) dp [0] * (C 1) for i in range(n): for cap in range(C, w[i] - 1, -1): dp[cap] max(dp[cap], dp[cap - w[i]] v[i]) return dp[C]空间复杂度从O(nC)降到O(C)。时间复杂度还是O(nC)因为每个状态还是要算一次。5.3 一维写法的常见变体与细节实际写代码的时候内层循环的边界有两种写法。一种是range(C, w[i]-1, -1)另一种是range(C, w[i]-1, -1)配合if cap w[i]的判断。前者更简洁后者更直观。我一般用前者因为少一层缩进。还有一个细节是物品下标的处理。二维写法里我用的是w[i-1]因为i从1开始一维写法里i从0开始直接用w[i]。两种写法都对但不要混着用否则很容易下标越界。注意一维压缩之后代码变得很短但可读性也下降了。如果你是在面试中写建议先写二维版本解释清楚状态定义和转移方程再说明可以压缩成一维。这样面试官能看到你的思路而不是只看到一个“背下来”的模板。6. 三种写法的对比与选型建议6.1 性能对比我把三种写法放在一起对比一下。测试环境是Python 3.10n 100C 1000物品重量和价值随机生成。写法时间复杂度空间复杂度实测耗时约适用场景暴力递归O(2^n)O(n)无法完成仅用于理解问题记忆化搜索O(nC)O(nC)0.15s递归思路清晰时二维递推O(nC)O(nC)0.08s需要保留完整表时一维压缩O(nC)O(C)0.05s生产环境首选暴力递归在n 100时完全跑不动因为2^100是天文数字。记忆化搜索和二维递推的时间差不多但记忆化搜索有递归开销实际会慢一些。一维压缩最快因为内存访问更集中缓存命中率更高。6.2 什么时候用哪种写法如果你是在学习阶段建议按“暴力递归 → 记忆化搜索 → 二维递推 → 一维压缩”的顺序走一遍。每一步都自己动手写、动手调不要跳步。跳步的后果就是“好像懂了但一写就错”。如果你是在面试中时间有限建议直接写一维压缩但要把思路讲清楚。面试官更看重你对状态定义和遍历顺序的理解而不是代码长度。如果你是在工程中需要根据具体场景选。如果C很大但n很小可以考虑用记忆化搜索加哈希表存状态避免开一个巨大的数组。如果n和C都很大那0/1背包本身就是NP难问题需要考虑近似算法或者问题本身的特殊结构。6.3 空间优化的边界一维压缩虽然省空间但有一个前提dp[cap]只依赖上一行的数据。如果转移方程依赖的是同一行的数据比如完全背包那一维压缩的遍历顺序就要改成正序。如果依赖的是多行的数据比如某些区间DP那一维压缩就不适用了。所以压缩之前一定要先看清楚转移方程的依赖关系。依赖上一行可以压缩依赖本行压缩后要注意顺序依赖多行老老实实开多维数组。7. 常见问题与排查技巧实录7.1 结果偏大大概率是遍历顺序错了这是0/1背包最常见的bug。一维写法里内层循环写成正序结果就会偏大因为物品被重复拿了。排查方法很简单用一个只有两件物品的小例子手动跑一遍看看dp数组的中间值。如果发现某个dp[cap]的值等于“同一件物品被拿了两次”的结果那就是顺序错了。7.2 结果偏小检查初始化如果dp数组初始化成了-1或者其他非零值结果可能偏小。0/1背包的dp数组应该全部初始化为0因为“不拿任何物品”的价值是0。如果题目要求“恰好装满背包”那初始化就要改dp[0] 0其他dp[cap] -inf。这个区别很关键面试中经常考。7.3 下标越界检查循环边界一维写法里内层循环的终止条件是w[i] - 1不是w[i]。因为range是左闭右开的range(C, w[i]-1, -1)会遍历到w[i]。如果写成range(C, w[i], -1)就会漏掉cap w[i]的情况结果偏小。7.4 递归爆栈改用递推或调高限制记忆化搜索在n很大时会爆栈。Python里可以用sys.setrecursionlimit(10000)临时解决但更稳妥的做法是改成递推。递推没有递归深度限制而且更快。7.5 常见问题速查表现象可能原因排查方法解决方法结果偏大内层循环正序用小例子手动跑改成倒序结果偏小初始化错误检查dp数组初值全部初始化为0下标越界循环边界写错打印i和cap终止条件用w[i]-1爆栈递归深度过大看n是否超过900改递推或调高限制超时用了暴力递归看时间复杂度改记忆化或递推实操心得调试DP代码的时候最有效的方法是把dp数组打印出来和手动填表的结果对比。找到第一个不一致的格子那个格子就是bug的源头。不要一上来就盯着代码看看半天也看不出问题。8. 从0/1背包延伸出去的几个方向0/1背包是动态规划的“母题”很多问题都是它的变体。比如完全背包每件物品可以拿无限次只需要把内层循环改成正序多重背包每件物品有数量限制可以拆成多个0/1背包或者用二进制优化分组背包每组只能选一件在遍历顺序上多一层循环。还有一类问题是“恰好装满”的变体。初始化的时候dp[0] 0其他设为负无穷最后如果dp[C]是负无穷就说明无法恰好装满。这个技巧在面试中很实用。另外0/1背包的“选或不选”思想可以推广到很多场景。比如子集和问题给一个数组问能否选出若干个数使和为target本质上就是价值等于重量的0/1背包。再比如分割等和子集也是同样的思路。我个人的体会是把0/1背包的四种写法都手写一遍比刷十道DP题都有用。因为这四种写法覆盖了动态规划的核心要素状态定义、转移方程、初始化、遍历顺序、空间优化。把这五个东西搞清楚了再去看其他DP问题会发现套路都是相通的。最后分享一个小技巧如果你在面试中遇到0/1背包的变体先不要急着写代码先用两分钟把状态定义和转移方程说清楚。状态定义对了代码就是水到渠成的事状态定义错了代码写得再漂亮也是错的。这个习惯我用了很多年帮我省下了不少调试时间。