上周朋友找我聊一个资源调度方案他手上有一批规格不同的服务器要跑一堆相互独立的任务每个任务占用的算力不同、带来的收益也不同在总算力固定的前提下怎么挑任务能让总收益最大。我听完第一反应是——这不就是背包问题嘛。但真正动手写的时候我才发现能把背包问题的动态规划解法讲清楚、写对还能延伸到各种变体场景的人远比想象中少。网上资料堆成山但大多是贴个状态转移方程就完事没人告诉你为什么倒序遍历、为什么初始化不同结果就完全不同。这篇就当成一次实战复盘来写。我尽量把背包问题的来龙去脉、常用套路、容易踩的坑都整理出来。不管你是准备算法面试还是工作中遇到了资源分配、任务取舍这类优化问题或者单纯想把动态规划彻底弄明白这篇应该都能帮上忙。1. 背包问题的真实面貌它到底在解决什么1.1 从装东西说起一个抽象出来的优化模型教科书上的标准描述是这样的给定一个容量为C的背包以及n个物品第i个物品有重量w[i]和价值v[i]问怎么选物品放进去让总价值最大同时总重量不超过C。但放在真实世界里背包可以是一台服务器物品是一个个要部署的服务模块背包也可以是一笔固定预算物品是一个个候选项目重量完全可能是时间、人力、带宽这类抽象资源价值则是收益、满意度、业务指标。我第一次意识到这个模型的普适性是在做一个广告位分配方案的时候几十个广告主每个广告主有不同的预算要求消耗的资源和预计收入带来的价值手上的广告位资源总量固定怎么分配才能让整体收入最大——本质上就是背包问题。所以背包问题不是一道题而是一个资源约束下的取舍模型。这也是为什么它在算法面试里出现频率很高——面试官看重的不是你背住了某个方程而是你能不能把一个实际问题抽象成这个模型。1.2 暴力枚举为什么行不通最朴素的想法很直接每个物品也就选和不选两种状态全部枚举一遍总共2^n种组合。n 20 的时候大概一百万种勉强能跑n 50 的时候就是千万亿级别跑上几十年也跑不完。就算加各种剪枝优化最坏情况下仍然是指数爆炸。我见过有人硬扛把所有组合用位运算枚举出来再逐个比较n 到 30 就明显卡顿了。这是背包问题最原始也最真实的痛点——候选集合稍微大一点暴力就彻底失效。动态规划之所以是标准解法就是因为它把指数级的枚举压缩成了多项式级的填表过程。1.3 怎么识别我遇到的其实是背包问题实战里最难的一步往往不是写代码而是认出问题。我总结下来一个场景如果同时满足下面三条大概率就能套背包模型有有限个候选对象比如任务、项目、物品每个都可以选择纳入或不纳入或者纳入几个。每个候选对象消耗一种或多种资源重量、容量、时间、钱都算。总资源有限目标是最大化收益。拿开头那个服务器调度例子来说候选是任务资源是算力收益是任务价值总算力固定。三条全部命中直接就是0-1背包。后面你会发现很多看似唬人的业务问题剥开外壳里面往往就是背包问题的某个变体。2. 动态规划是怎么长出来的从递归到填表2.1 先写递归把装还是不装拆开看很多讲DP的文章直接甩状态转移方程读者看得一脸懵。我的习惯是先写递归再想怎么优化。背包问题的递归思路特别自然。定义一个函数F(i, c)用前i个物品填一个容量为c的背包能得到的最大价值。现在来看第i个物品只有两条路不装它那问题就变成F(i-1, c)跟没有这个物品一样。装它前提是c w[i]装进去之后背包剩下的容量是c - w[i]价值加上v[i]前面i-1个物品继续填剩下的空间即F(i-1, c-w[i]) v[i]。取这两者的较大值就是对第i个物品的最优决策。写成代码就是经典的递归def knapsack_recursive(i, c, weights, values): if i 0: return 0 if c 0: return 0 # 不装第 i 个 best knapsack_recursive(i - 1, c, weights, values) # 装第 i 个 if c weights[i]: best max(best, knapsack_recursive(i - 1, c - weights[i], weights, values) values[i]) return best这段代码本身就能跑n 小的时候没毛病。但它的致命弱点是重复计算同一个(i, c)状态会被多次求解。2.2 重叠子问题递归低效的真正原因举个例子假设有三个物品你在递归树里会反复遇到F(1, 8)这种状态。很可能从F(2, 10)走不装来到它又从F(2, 9)走装也来到它。每次都会把整个子树重新算一遍。这就是动态规划里常说的重叠子问题。既然同一个状态的结果是固定的算过一次存下来下次直接查表不就节省了大量时间这种递归 缓存的写法叫记忆化搜索也叫自顶向下的DP。memo {} def knapsack_dfs(i, c, weights, values): key (i, c) if key in memo: return memo[key] if i 0 or c 0: return 0 best knapsack_dfs(i - 1, c, weights, values) if c weights[i]: best max(best, knapsack_dfs(i - 1, c - weights[i], weights, values) values[i]) memo[key] best return best到这一步时间复杂度已经优化到了O(n * C)因为状态总数差不多就是(i, c)的组合数。但记忆化递归还有个问题递归深度受系统栈限制n到几千的时候容易栈溢出而且自顶向下的递归开销比填表大不少空间优化后面要讲的滚动数组也不好展开。所以工程上更推崇另一个方向。2.3 自底向上填表DP的真正形态既然状态是二维的那就直接开一张二维表从最小的子问题开始一层层往上填。这张表里每一格dp[i][j]的含义和F(i, j)完全一样前 i 个物品容量为 j 的背包能取得的最大价值。初始化的时候dp[0][...] 0一个物品都不放价值自然是0。然后遍历每个物品、每个容量用递推关系填格dp[i][j] max( dp[i-1][j], # 不装第 i 个物品 dp[i-1][j-w[i]] v[i] # 装第 i 个物品j w[i] 时 )这就是状态转移方程。一张 n 行、C1 列的表每个格子只依赖上一行同一列和上一行左侧某个位置的数据填表顺序自然是从上到下、从左到右。所有格子填完dp[n][C]就是答案。理解这张表非常关键。每当我看到有人背下转移方程但不会做题基本都是在填表这一步没有形成直观画面。你可以自己拿小例子手动画一遍表比如 3 个物品、容量 5把每个格子都写出来之后再看任何背包题都会觉得顺眼得多。3. 0-1背包的完整实战从二维DP到一维滚动数组3.1 先上二维版本正确性优先实战里我建议先在纸上推演二维版本跑通正确性再做空间优化。下面是标准的二维实现def knapsack_0_1_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(1, 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]代码里有两个容易忽略的细节dp 数组尺寸是(n1) x (capacity1)多出来的一行一列是给没有物品和容量为0留的边界。内层循环的j从1开始但j0时结果也是0所以实际从0开始或者从1开始都一样。只不过如果存在重量为0的物品你必须单独处理j0的状态后面我会专门讲这个坑。二维版本的时间和空间复杂度都是O(n * C)。当 n 和 C 都是几千的时候内存轻松到几千万个数Python 里就是几百MB直接爆掉。这时候必须做空间优化。3.2 空间优化为什么必须倒序遍历观察转移方程可以发现dp[i][...]只依赖dp[i-1][...]。也就是说我只需要保留上一行的数据当前行可以不断覆盖上一行——这就是滚动数组。更进一步直接用一维数组dp[j]把容量那一维单独留下来dp[j] max(dp[j], dp[j - w] v)但这里有个致命细节内层循环必须倒序遍历。为什么因为一维数组在更新dp[j]时dp[j-w]在倒序情况下还没有被本轮更新它仍然是上一轮处理上一个物品时的状态——这正好对应当前物品还没被取过。如果正序dp[j-w]已经被本轮更新过了它已经包含了当前物品被取了一次甚至多次的信息再叠加一次价值就相当于同一个物品可以无限取用——那是完全背包的语义不是0-1背包。我拿一个极端例子验证。容量3只有一个物品重量2、价值3。倒序跑j3时dp[3] max(dp[3], dp[1] 3) 3j2时dp[2] max(dp[2], dp[0] 3) 3。最终dp[3] 3正确。正序跑j2时dp[2] 3j3时dp[3] max(dp[3], dp[2] 3) 6。同一个物品变成拿两次了明显错误。一维版本def knapsack_0_1_1d(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]空间从O(n*C)降到了O(C)这是实战中最常用的形态。面试手写背包题直接上一维版本基本就是标准答案。但前提是你心里清楚一维数组的语义和倒序的原因不然换个变体题就蒙了。3.3 初始化到底填什么一个容易被忽略的分水岭很多人在初始化这里栽跟头。同样是dp数组初始化的方式决定了你的DP是不超过容量还是恰好装满。不超过容量全部填0。因为任何容量下什么都不装这个方案都合法价值为0。恰好装满dp[0] 0其他所有容量初始化为负无穷比如-float(inf)。因为只有容量0能由空背包恰好达到其他容量在当前状态下是不可达的。负无穷的意义是从不可达状态转移出来的结果仍然是不可达。做完DP之后如果dp[capacity]仍然是负无穷说明不存在恰好装满的方案。举个例子恰好装满版初始化就是dp [-float(inf)] * (capacity 1) dp[0] 0然后转移逻辑完全不变。这个初始化细节在实际业务里很重要。比如你做预算分配要求把预算刚好花完评估不同项目组合的收益那就是恰好装满如果不要求花完就是不超过容量。我见过不少人在初始化上栽跟头查了很久才发现只差这一行。4. 完全背包与多重背包变体问题的处理套路4.1 完全背包把内层循环方向反过来完全背包说的是每个物品可以无限取用。最朴素的想法是在0-1背包的基础上再套一层循环枚举当前物品取了多少件dp[i][j] max(dp[i-1][j - k*w[i]] k*v[i])k从0到 j//w[i]这个复杂度是O(n*C*C/w)数据稍大就完蛋。但观察一下如果你在一维数组里正序遍历容量会发生什么正序遍历时dp[j-w]已经被本轮更新过了也就是说当前物品已经被算过一次甚至更多次。这正是可以重复取用一个物品的语义。所以完全背包的解法非常简洁就是0-1背包把内层循环倒序改成正序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]我第一次理解这个对比的时候觉得动态规划真的巧妙0-1背包和完全背包代码只差一行本质就在于一维数组更新时用的是旧值还是新值。这个点如果之前没想明白建议自己拿小例子手动跑一遍正序循环感受一下重复更新的过程。4.2 多重背包二进制拆分把有限多次转成0-1多重背包是每个物品最多取c[i]件。最呆的办法是把每个物品拆成c[i]个独立物品变成一个0-1背包。但c[i]如果很大——比如10万——拆出来的物品数量爆炸内存和时间都受不了。这时候用二进制拆分把c[i]拆成若干个二进制组比如13拆成1、2、4、6这些数字任意组合能覆盖0到13之间的所有整数。然后把每组当成一个新物品重量和价值都乘以组大小跑0-1背包即可。为什么这样可行因为任何0到13之间的取用数量都可以用1、2、4、6中选几个加起来凑出来比如5149126。这个原理在于二进制表示法任意整数都能表示为若干个2的幂之和最后可能多一个零头拆出来即可。这样原来需要展开成c[i]个物品的地方优化到了O(log c[i])个。def knapsack_multiple(weights, values, counts, capacity): items [] for w, v, c in zip(weights, values, counts): k 1 while c 0: take min(k, c) items.append((w * take, v * take)) c - take k 1 # 转换成 0-1 背包 dp [0] * (capacity 1) 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]二进制拆分的正确性值得多说一句。拆出来的组看似只有十几个但它们的组合覆盖了整个[0, c]区间。这个结论的证明思路很直接从低位往高位看1、2、4...这些2的幂能表示所有小于它们之和的数最后剩下的那个零头再补上就完整了。我建议在代码里写上注释过两个月回头看还能想起来为什么这么拆。4.3 三类背包问题怎么快速记忆和区分我平时给朋友讲的时候会画一张对比表把三者放一起对比着记类型物品使用限制一维内层循环方向时间复杂度0-1背包每件最多1次倒序O(n*C)完全背包每件无限次正序O(n*C)多重背包每件有限 c 次倒序 二进制拆分O(nClog max_c)这张表的关键记忆锚点是倒序 从旧状态推出新状态 禁止重复用当前物品正序 从新状态推新状态 支持重复用。再往深一层多重背包经过二进制拆分后本质就是0-1背包所以也用倒序。遇到混合场景也不要慌。比如一类物品有限、一类无限你可以把有限类拆完和无限类分开处理再合并结果。实际项目中很少考纯粹某一种背包更多是这些概念组合着来。5. 实战中躲不开的坑回溯方案、边界条件和调试手段5.1 不光要最大价值还要知道选了哪些物品很多实战场景不只是最大值是多少而是哪些任务应该被选上。比如你把方案告诉朋友他肯定要问那具体选哪几个服务二维DP天然支持回溯。处理完所有物品后从dp[n][capacity]往回走如果dp[i][j] dp[i-1][j]说明第i个物品被选了把它的编号记下来j减去它的重量继续往前查。否则说明没选它直接看上一行。def knapsack_with_path(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(1, 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] # 回溯路径 chosen [] j capacity for i in range(n, 0, -1): if dp[i][j] dp[i - 1][j]: chosen.append(i - 1) j - weights[i - 1] chosen.reverse() return dp[n][capacity], chosen一维滚动数组因为每行都被覆盖DP过程中没有保存决策信息所以回溯比较麻烦。我的做法是在一维基础上额外开一个choice[i][j]布尔表专门记录每个状态是否选择了第i个物品。这是空间换时间、换可解释性的典型例子。做业务方案的时候决策的可解释性往往比省那点内存更重要。5.2 几个容易翻车的边界条件背包问题的代码很短但边界条件特别考验经验。下面这几个我都踩过物品重量为0如果w[i] 0那这个物品取多少次都不占容量一维倒序循环会直接卡在range(capacity, -1, -1)里不断更新同一个dp[j]可能写出死循环或者错误结果。处理方法很粗暴但有效把重量为0、价值为正的物品单独拿出来先把价值累加到答案里剩下的正重量物品再做背包。容量极大、物品很少比如容量是10的9次方n只有30个直接开O(n*C)的表就爆了。这种场景要转换思路按价值做DPdp[k]表示凑到价值k需要的最小容量价值范围是sum(values)最后在可行范围内找最大价值。这是另一个经典套路面试里偶尔会考。恰好装满变体前面说过初始化负无穷。在判断是否可行时不能直接拿dp[capacity]和0比较要判断它是否仍然是负无穷。很多实现里用很大的负数-1e9代替-float(inf)也是为了避免浮点数运算的坑。总重量小于等于容量这种情况答案就是所有物品价值之和可以直接返回没必要跑DP。5.3 一个亲测好用的调试方法小样例手动填表我调试DP题有一个固定流程99%的逻辑错误都能用这个方法揪出来拿一个容量很小的例子比如5以内手动把二维表画出来再跟程序跑出来的表逐格对比。比如容量5物品是(重量2, 价值3)、(重量3, 价值4)我手工填一遍表各种转移关系一目了然。程序输出不一样的时候对照对比很快就能发现是初始化写错、循环边界写错还是转移方程写错。这比对着代码干瞪眼有效得多。这个习惯我保持了很久包括帮朋友排查问题的时候也这么干。人肉执行一遍DP你对状态定义的理解会彻底固化之后遇到任何变体都不虚。5.4 再谈实际业务从抽象到落地回到开头那个服务器调度场景。把任务抽象成物品之后代码很快就跑出了最优收益和任务清单。但实际落地还会遇到业务约束某些任务不能同时跑、某些任务有优先级权重、资源不是单一维度而是CPU内存双维度。这些约束不是背包问题的范围内但在真实系统里几乎都会出现。我的经验是先把核心约束抽象成标准背包模型快速得到一个合理基线方案再针对额外约束做局部修正。比如不能同时跑可以用互斥条件做后处理过滤多维度资源可以尝试按主资源做背包、用次资源做可行性校验。这种先模型化、再修正的思路比试图把每个约束都揉进状态转移方程里要实用得多。6. 最后分享一些自己的经验背包问题真正难的地方不在代码本身而在于你能不能把一个陌生问题还原成这个熟悉模型。我现在的习惯是遇到任何在有限资源下做取舍、求最大收益的问题先问自己三件事有多少个候选对象每个候选消耗什么资源总资源限制是多少如果答案都清晰基本就是背包问题直接套上对应的DP框架去解。另外一个体会是动态规划不是靠背模板学会的。把二维表手工填一遍、把一维优化前后的代码跑一遍、把三种背包的循环方向改来改去对比一遍这些实际操作比看上几十篇文章都管用。我第一次彻底理解倒序和正序的区别就是因为拿两组代码反复跑同一个用例看到那个被取多次的结果时才真正明白为什么。如果你正准备面试建议把0-1背包、完全背包、多重背包的代码各默写几遍再把回溯路径和恰好装满这两个衍生问法练熟。这几个点覆盖了我见过的绝大多数背包相关考题。遇到没见过的变体先冷静回到状态定义本身想清楚每个格子的含义再动手写转移方程——这一整套流程下来我相信你在背包问题上不会再虚。