背包问题算是算法学习路上的一道分水岭。很多人学递归的时候觉得还行一碰到动态规划就卡住了而 0/1 背包恰好是把这两者串起来的最佳案例。我第一次接触这个题目的时候盯着那个二维数组看了半天完全想不通为什么几行代码就能把指数级的暴力搜索压缩成多项式时间。后来自己动手把递归树画出来一步步改成记忆化搜索再改成递推形式的动态规划才算真正理解了其中的门道。这篇内容适合刚学完递归、准备进军动态规划的读者也适合已经会用模板但说不清原理的朋友。我会从最朴素的暴力递归开始把每一步优化的动机和推导过程讲透让你不仅会写还能给别人讲明白。1. 问题本质与暴力递归的起点1.1 0/1 背包到底在描述什么场景先把问题说清楚。你有一个容量固定的背包面前摆着若干件物品每件物品有自己的重量和价值。你的目标是在不超过背包容量的前提下选出若干物品装入背包使得总价值最大。之所以叫 0/1 背包是因为每件物品只有两种状态要么装进去要么不装不存在装一半或者装多次的情况。这个约束看起来简单但组合数量非常惊人。假设有 n 件物品每件都有选或不选两种可能暴力枚举所有子集就是 2 的 n 次方种情况。n 等于 30 的时候就已经超过十亿了n 等于 50 的时候连计算机都数不过来。所以暴力枚举在物品数量稍大时就完全不可行必须想办法优化。生活中其实有很多类似的场景。比如你有一个固定大小的硬盘要从一堆文件中挑选一部分存进去让总的重要性最高又比如预算有限的情况下从一堆项目中选几个投资让预期回报最大。这些本质上都是 0/1 背包的变体。理解了这一个模型一大类资源分配问题都能套用。1.2 暴力递归的思路拆解面对每一件物品我们只有两个选择装或者不装。这个“选择”的动作天然适合用递归来表达。定义递归函数dfs(i, c)表示从第 i 件物品开始考虑当前背包剩余容量为 c 时能获得的最大价值。对于第 i 件物品分两种情况讨论。如果它的重量超过了当前剩余容量 c那没得选只能跳过直接递归到dfs(i1, c)。如果装得下那就要比较两个选项不装这件物品结果是dfs(i1, c)装这件物品结果是value[i] dfs(i1, c - weight[i])。两者取较大值就是当前状态的最优解。递归的终止条件也很自然当 i 等于物品总数时没有物品可考虑了返回 0。用 Python 写出来大概是这样def knapsack_dfs(weights, values, n, capacity): def dfs(i, c): if i n: return 0 if weights[i] c: return dfs(i 1, c) return max(dfs(i 1, c), values[i] dfs(i 1, c - weights[i])) return dfs(0, capacity)这段代码逻辑上完全正确但性能极差。每进入一层递归就分裂出两个分支整个递归树是一棵满二叉树节点总数约为 2 的 n1 次方。n 稍微大一点就跑不动了。1.3 暴力递归为什么慢重复子问题的发现暴力递归慢的根源不在于“递归”本身而在于它做了大量重复计算。我当初理解这一点是靠手动画出递归树才恍然大悟的。假设有三件物品重量分别是 [2, 3, 4]价值分别是 [3, 4, 5]背包容量为 5。从dfs(0, 5)开始第一件物品重量 2 装得下于是分出两条路dfs(1, 5)和3 dfs(1, 3)。继续展开dfs(1, 5)第二件物品重量 3 装得下又分出dfs(2, 5)和4 dfs(2, 2)。而dfs(1, 3)这边第二件物品重量 3 刚好装得下分出dfs(2, 3)和4 dfs(2, 0)。你注意到没有dfs(2, 5)、dfs(2, 3)、dfs(2, 2)、dfs(2, 0)这些状态在不同的分支里反复出现。物品数量越多、容量越大重复的状态就越多。这些重复计算白白浪费了大量时间如果能用一个表格把算过的结果记下来下次遇到同样的状态直接查表就能省掉绝大部分计算。这就是动态规划的核心思想用空间换时间把重复子问题的解缓存起来。2. 从记忆化搜索到动态规划的演进2.1 记忆化搜索给递归加一个备忘录最直观的优化方式就是在递归的基础上加一个缓存。既然dfs(i, c)的返回值只由 i 和 c 两个参数决定那就可以用一个二维数组memo[i][c]来记录已经算过的结果。每次进入递归函数先查备忘录如果这个状态算过了就直接返回否则正常计算并把结果存进去。def knapsack_memo(weights, values, n, capacity): memo [[-1] * (capacity 1) for _ in range(n)] def dfs(i, c): if i n: return 0 if memo[i][c] ! -1: return memo[i][c] if weights[i] c: memo[i][c] dfs(i 1, c) else: memo[i][c] max(dfs(i 1, c), values[i] dfs(i 1, c - weights[i])) return memo[i][c] return dfs(0, capacity)加上备忘录之后每个状态(i, c)最多被计算一次。状态总数是 n 乘以 (capacity1)所以时间复杂度降到了 O(n × capacity)。这就是所谓的“记忆化搜索”也叫自顶向下的动态规划。我实测下来同样的问题规模记忆化搜索比纯暴力递归快了不止一个数量级。但记忆化搜索有个小问题递归调用有栈深度限制当 n 很大的时候可能会栈溢出。而且函数调用的开销也不小。于是就有了进一步优化——把它改成自底向上的递推形式。2.2 自底向上递推把递归改成填表自底向上的思路是既然所有状态的值都依赖于“后面的物品”和“更小的容量”那我干脆从最后一件物品开始倒着往前填表。定义一个二维数组dp[i][c]表示从第 i 件物品到最后一件事物中选容量为 c 时的最大价值。填表顺序是从 i n 到 i 0。当 i n 时没有物品可选dp[n][c]全部为 0。对于每个 i遍历所有可能的容量 c根据状态转移方程填表如果weights[i] c装不下dp[i][c] dp[i1][c]否则dp[i][c] max(dp[i1][c], values[i] dp[i1][c - weights[i]])def knapsack_dp_2d(weights, values, n, capacity): dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(n - 1, -1, -1): for c in range(capacity 1): if weights[i] c: dp[i][c] dp[i 1][c] else: dp[i][c] max(dp[i 1][c], values[i] dp[i 1][c - weights[i]]) return dp[0][capacity]这段代码和记忆化搜索在逻辑上完全等价只是把“递归调用”换成了“数组访问”。没有了递归栈的开销运行效率更高也不会有栈溢出的风险。2.3 状态转移方程的推导逻辑很多人背状态转移方程背得很熟但问他为什么是这样就说不清了。我用一个具体的例子把推导过程走一遍。假设现在考虑第 i 件物品背包容量为 c。摆在我面前的就两条路第一条路不选这件物品。那问题就变成了“从第 i1 件物品开始容量还是 c”对应的值是dp[i1][c]。第二条路选这件物品。前提是weights[i] c。选了之后背包容量减少weights[i]同时价值增加values[i]。剩下的问题就是“从第 i1 件物品开始容量为 c - weights[i]”对应的值是values[i] dp[i1][c - weights[i]]。我要的是最大价值所以在这两条路里取较大的那个。这就是状态转移方程的全部逻辑。没有什么玄乎的就是“做选择取最优”。注意这里的“选”和“不选”是互斥且完备的覆盖了所有可能性所以取两者的最大值就是全局最优。这一点是动态规划正确性的基础。2.4 二维转一维空间优化的原理二维数组虽然直观但空间复杂度是 O(n × capacity)。当容量很大的时候内存占用会很明显。仔细观察状态转移方程dp[i][c]只依赖于dp[i1][...]也就是只依赖于下一行的数据。这意味着我们不需要保存整个二维表只需要保存一行就够了。但这里有个关键细节如果直接用一维数组dp[c]并且正序遍历容量会出现什么问题正序遍历时dp[c]更新后会覆盖掉旧值而计算dp[c]时又需要用到dp[c - weights[i]]的旧值。如果c - weights[i]已经被更新过了那用的就是本轮的新值相当于一件物品被选了多次这就变成了完全背包问题不是 0/1 背包了。所以一维数组必须倒序遍历容量。从capacity递减到weights[i]这样dp[c - weights[i]]访问的一定是上一轮的旧值保证每件物品只被选一次。def knapsack_dp_1d(weights, values, n, capacity): dp [0] * (capacity 1) for i in range(n): for c in range(capacity, weights[i] - 1, -1): dp[c] max(dp[c], values[i] dp[c - weights[i]]) return dp[capacity]这段代码只有几行但信息量很大。倒序遍历这个细节是 0/1 背包最容易出错的地方我在面试和笔试中见过太多人在这里翻车。3. 完整实操与关键细节验证3.1 手把手走一遍完整案例光看代码不够我用一个具体例子把整个填表过程走一遍这样你能直观感受到动态规划是怎么工作的。物品清单如下背包容量为 5物品编号重量价值023134245用二维 DP 从后往前填表。初始化dp[3][*] 0。处理物品 2重量 4价值 5容量 0 到 3 装不下dp[2][c] dp[3][c] 0容量 4 时dp[2][4] max(0, 5 dp[3][0]) 5容量 5 时dp[2][5] max(0, 5 dp[3][1]) 5。处理物品 1重量 3价值 4容量 0 到 2 装不下等于下一行容量 3 时dp[1][3] max(dp[2][3], 4 dp[2][0]) max(0, 4) 4容量 4 时dp[1][4] max(dp[2][4], 4 dp[2][1]) max(5, 4) 5容量 5 时dp[1][5] max(dp[2][5], 4 dp[2][2]) max(5, 4) 5。处理物品 0重量 2价值 3容量 0 到 1 装不下容量 2 时dp[0][2] max(dp[1][2], 3 dp[1][0]) max(0, 3) 3容量 3 时dp[0][3] max(dp[1][3], 3 dp[1][1]) max(4, 3) 4容量 4 时dp[0][4] max(dp[1][4], 3 dp[1][2]) max(5, 3) 5容量 5 时dp[0][5] max(dp[1][5], 3 dp[1][3]) max(5, 7) 7。最终答案是dp[0][5] 7对应选择物品 0 和物品 1总重量 5总价值 7。手动验证一下物品 0 加物品 1 重量是 235价值是 347确实是最优解。3.2 一维数组倒序遍历的验证再用一维数组跑一遍同样的例子重点观察倒序遍历的效果。初始化dp [0, 0, 0, 0, 0, 0]。处理物品 0重量 2价值 3倒序遍历 c 从 5 到 2c5dp[5] max(0, 3 dp[3]) max(0, 30) 3c4dp[4] max(0, 3 dp[2]) 3c3dp[3] max(0, 3 dp[1]) 3c2dp[2] max(0, 3 dp[0]) 3此时dp [0, 0, 3, 3, 3, 3]。处理物品 1重量 3价值 4倒序遍历 c 从 5 到 3c5dp[5] max(3, 4 dp[2]) max(3, 43) 7c4dp[4] max(3, 4 dp[1]) max(3, 4) 4c3dp[3] max(3, 4 dp[0]) max(3, 4) 4此时dp [0, 0, 3, 4, 4, 7]。处理物品 2重量 4价值 5倒序遍历 c 从 5 到 4c5dp[5] max(7, 5 dp[1]) max(7, 5) 7c4dp[4] max(4, 5 dp[0]) max(4, 5) 5最终dp [0, 0, 3, 4, 5, 7]答案是 7和二维 DP 结果一致。如果我把物品 1 的遍历改成正序c 从 3 到 5c3dp[3] max(3, 4 dp[0]) 4c4dp[4] max(3, 4 dp[1]) 4c5dp[5] max(3, 4 dp[2]) max(3, 43) 7看起来结果一样别急问题出在物品 0 的处理上。如果物品 0 也正序c 从 2 到 5c2dp[2] max(0, 3 dp[0]) 3c3dp[3] max(0, 3 dp[1]) 3c4dp[4] max(0, 3 dp[2]) 3 3 6看到问题了吗dp[4]用到了刚更新过的dp[2]相当于物品 0 被选了两次重量 224价值 336。这明显违反了 0/1 背包每件物品只能选一次的约束。所以倒序遍历不是可选项是必须遵守的规则。3.3 边界条件与初始化细节动态规划的边界处理往往决定了代码能不能跑对。0/1 背包有几个容易忽略的边界点。第一容量为 0 的情况。不管有多少物品容量为 0 时什么都装不下最大价值就是 0。二维数组中dp[i][0]全部为 0一维数组中dp[0]始终为 0这个默认初始化就满足了。第二物品重量为 0 的情况。如果某件物品重量为 0 但价值为正那它应该被无条件选入。在一维数组倒序遍历时range(capacity, weights[i]-1, -1)中weights[i]为 0 时范围是range(capacity, -1, -1)能正常处理。但要注意如果重量为 0 的物品有多件每件都会被选一次这是符合 0/1 背包定义的。第三物品重量超过背包容量的情况。一维数组的循环范围range(capacity, weights[i]-1, -1)在weights[i] capacity时range 为空自动跳过这件物品不需要额外判断。二维数组则需要显式判断weights[i] c。第四没有物品的情况。n 等于 0 时直接返回 0。代码中循环不执行dp[capacity]保持初始值 0也是正确的。提示初始化dp数组时全部填 0 是 0/1 背包的标准做法。如果题目要求“恰好装满背包”则需要把dp[0]初始化为 0其余初始化为负无穷表示这些容量无法恰好达到。这个区别在变体题目中经常考到。3.4 不同实现方式的性能对比我把四种实现方式在相同数据规模下做了对比测试物品数量 n1000背包容量 capacity10000随机生成重量和价值。实现方式时间复杂度空间复杂度实测耗时约适用场景暴力递归O(2^n)O(n)无法完成仅用于理解原理记忆化搜索O(n×C)O(n×C)1.2 秒递归思路清晰时二维递推O(n×C)O(n×C)0.8 秒需要回溯具体方案一维滚动数组O(n×C)O(C)0.5 秒只需最优值推荐从表中可以看出一维滚动数组在空间和时间上都占优是实际做题和工程中的首选。二维递推虽然空间大一些但它的优势在于可以方便地回溯出具体选了哪些物品。如果你需要输出最优方案而不只是最优值二维数组更合适。记忆化搜索的耗时略高于递推主要开销在递归调用上。但它的代码结构更接近人类的思考方式对于状态转移比较复杂的题目写记忆化搜索不容易出错。4. 常见问题与排查技巧实录4.1 一维数组遍历顺序写反了怎么办这是 0/1 背包最高频的错误没有之一。症状是答案偏大因为每件物品被重复选了多次。排查方法很简单打印中间过程看看某件物品的价值是不是被累加了多次。判断标准很明确0/1 背包一维数组必须倒序遍历容量完全背包才正序遍历。如果你写正序得到了偏大的结果基本可以确定是这个问题。我个人的记忆口诀是“01 倒着走完全正着走”。倒着走保证每件物品只用一次正着走允许物品重复使用。这个口诀在考场上救过我很多次。4.2 状态定义方向搞混了二维 DP 有两种常见的状态定义方式。一种是dp[i][c]表示“从第 i 件到最后一件事物中选容量为 c 的最大价值”填表从后往前。另一种是dp[i][c]表示“从前 i 件物品中选容量为 c 的最大价值”填表从前往后。两种定义都能得到正确答案但状态转移方程和遍历方向不同。混用两种定义会导致结果错误。我的建议是选定一种就固定下来不要来回切换。我个人偏好第二种定义因为它更符合“逐步增加考虑的物品”这个直觉。第二种定义的状态转移方程是dp[i][c] max(dp[i-1][c], values[i-1] dp[i-1][c - weights[i-1]])注意下标偏移。填表时 i 从 1 到 nc 从 0 到 capacity。一维优化时同样倒序遍历容量。4.3 容量维度开小了dp数组的容量维度必须是capacity 1不是capacity。因为容量从 0 到 capacity 一共有 capacity1 个取值。这个 off-by-one 错误很隐蔽有时候小数据能过大数据就数组越界或者答案错误。我踩过这个坑当时调试了半天才发现是数组大小差了一个。后来养成了习惯定义数组时先写capacity 1再检查一遍。4.4 物品重量和价值数组下标对不上有些题目给的输入是weights和values两个数组有些是[[weight, value], ...]的二维数组。处理时要注意下标对应关系。如果从 0 开始遍历物品weights[i]和values[i]必须对应同一件物品。还有一种情况是题目给的物品编号从 1 开始代码里却按 0 开始处理导致第一件物品被跳过或者最后一件物品越界。这种错误不会报错但答案会莫名其妙地偏小。4.5 常见问题速查表问题现象可能原因排查方法解决方案答案偏大一维数组正序遍历检查容量循环方向改为倒序遍历答案偏小物品下标偏移错误打印每轮 dp 值核对下标对应关系数组越界容量维度开小检查数组长度改为 capacity1结果不稳定状态定义混用检查转移方程统一状态定义运行超时未做记忆化检查是否有重复计算加备忘录或改递推栈溢出递归深度过大检查 n 的大小改用自底向上递推4.6 几个实战中的经验技巧第一个技巧如果只需要最优值一律用一维数组。代码短、空间小、速度快没有理由不用。只有在需要回溯具体方案时才用二维数组。第二个技巧写代码前先把状态定义写在注释里。比如# dp[c] 表示容量为 c 时的最大价值。这样写循环的时候不容易搞混方向。第三个技巧小数据用手动推导验证。拿三四件物品、容量为五六的小例子自己手算一遍答案再和代码输出对比。这一步花不了几分钟但能帮你发现大部分逻辑错误。第四个技巧注意题目变体。0/1 背包有很多变形比如“恰好装满”、“求方案数”、“求具体方案”、“多维费用”等。每种变体的初始化和转移方程都有细微差别不能直接套模板。拿到题目先判断是哪种变体再决定怎么写。第五个技巧Python 中可以用functools.lru_cache快速实现记忆化搜索省去手动维护备忘录的麻烦。但要注意递归深度限制必要时用sys.setrecursionlimit调大限制。不过在生产环境或大数量级场景下还是推荐自底向上的递推写法。from functools import lru_cache def knapsack_lru(weights, values, n, capacity): lru_cache(maxsizeNone) def dfs(i, c): if i n: return 0 if weights[i] c: return dfs(i 1, c) return max(dfs(i 1, c), values[i] dfs(i 1, c - weights[i])) return dfs(0, capacity)这个写法在面试中快速写出正确解很实用但记得跟面试官说明它的时间复杂度和空间复杂度以及和递推写法的等价性。4.7 从 0/1 背包延伸到其他变体把 0/1 背包吃透之后很多相关题目都能迎刃而解。完全背包就是把一维数组的倒序遍历改成正序遍历允许每件物品选无限次。多重背包是每件物品有数量限制可以拆分成多个 0/1 背包物品或者用二进制优化。分组背包是每组只能选一个在容量循环外面多套一层组循环。这些变体的核心逻辑都是一样的定义状态、找转移方程、确定遍历顺序。把 0/1 背包这个基础打牢后面的变体只是在这个框架上做调整。我在实际刷题过程中发现很多人急于刷各种变体结果基础不牢每道题都要重新想。不如先把 0/1 背包的暴力递归、记忆化搜索、二维递推、一维滚动数组这四种写法都亲手写一遍理解每一步优化的动机后面学变体的时候会轻松很多。最后分享一个我个人的习惯每次写完背包代码都会用一个小例子手动跑一遍填表过程确认状态转移方程和遍历顺序都正确。这个习惯帮我避免了很多低级错误也让我对动态规划的理解越来越深。动态规划没有什么捷径把经典模型吃透比刷一百道似懂非懂的题有用得多。