动态规划入门：01背包问题与状态转移方程详解

我自己当初学动态规划绕了挺大一圈弯路。看了一堆“状态转移方程”的帖子脑子里全是“这玩意儿到底怎么来的”的疑问直到自己动手把一张二维表格一格一格填完才突然通了。背包问题尤其是01背包就是捅破这层窗户纸最好的那个手指头。这篇文章不打算给你堆数学公式我尽量用大白话把动态规划DP和背包问题的来龙去脉讲清楚。你会搞清楚三件事背包问题到底在干嘛、状态转移方程是怎么“憋”出来的、以及为什么那个一维数组的遍历顺序是反的。不管你是准备面试、打比赛还是纯粹想锻炼思维这篇都能给你一个能直接上手的思考框架。1. 背包问题为什么是动态规划的最佳入门很多人学DP第一个接触的就是背包这不是没道理的。因为背包问题把所有DP的核心要素都凑齐了一个明确的目标装价值最大、一堆有限制的选择容量有限、还带着一个“选与不选”的决策过程。它足够简单让你能一眼看穿DP的骨架但又足够典型能衍生出几十种工业级的变种。1.1 先搞懂背包问题的“江湖地位”背包问题本质上是一个资源分配问题。你有一个容量有限的包面前有一堆物品每件物品有自己的重量和价值目标是在不超重的前提下让包里东西的总价值最高。这个描述听起来是不是很像很多现实场景双十一凑满减怎么凑手上的预算怎么分配给多个项目才能收益最大化有限的带宽怎么分配给不同的服务甚至是给你的电脑硬盘规划分区都能抽象成一个背包模型。也正因为它的抽象能力极强背包问题成了算法面试和竞赛里的常客。从最基础的01背包到完全背包、多重背包、分组背包再到它们的各种魔改求方案数、恰好装满、二维费用每一层都能卡住一大批人。而这一切的高楼大厦全都建立在今天要讲的这块地基上——最最简单的01背包。1.2 从暴力破解到动态规划思路是怎么进化的如果让你用最朴素的办法解决背包问题你会想到什么那就是枚举。每件物品只有“拿”和“不拿”两种状态所以N件物品一共就有2^N种组合。这就是暴力搜索数据量小还好一旦物品数量超过20运行时间就能让你等到怀疑人生。为什么暴力搜索这么慢因为它重复计算了太多相同的子问题。假设你正在决策第5件物品拿不拿无论第1、2件物品怎么选的一旦确定了它们对容量的占用后面面临的决策完全是一模一样的。可惜暴力搜索会把这些相同的状态从头到尾再算一遍。动态规划的伟大之处就在于它把“算过的结果存下来下次直接用”。背包问题正好满足DP的两个适用条件最优子结构前N件物品在容量C下的最优解必然包含前N-1件物品在某个容量C下的最优解。你不需要关心C是怎么来的只需要信任它已经是那个子问题的最佳答案就行。重叠子问题不同的选择路径会走到相同的大容量、少物品的小状态上。只要这两个特性成立我们就能把指数级的暴力枚举压缩成多项式级别的填表游戏。这个“填表”的过程就是动态规划的核心形态。2. 01背包全解析从二维DP到一维优化“01”这个名字指的是每件物品的状态非0即1取或者不取不存在“取半个”这种说法。它是所有背包问题里最基础、也是最重要的一种。后面你会看到完全背包和多重背包的代码本质就是01背包代码上的一点小改动。2.1 状态定义与转移方程的“憋”法在写代码之前最重要的是先搞清楚状态怎么定义。所谓状态就是我们在解决问题的过程中需要记录的关键信息。一个很自然的想法是用dp[i][j]表示“前i件物品恰好放入一个容量为j的背包里能获得的最大价值”。注意我这里的措辞是“恰好放满”还是“不超过容量”这会导致初始化方式完全不同后面会专门讲这个坑。状态定义好了现在想转移方程。面对第i件物品你有两个选择不拿那简直太轻松了当前的价值就等于前i-1件物品在容量j下的最优解即dp[i][j] dp[i-1][j]。拿代价是你得为它腾出w[i]的空间。所以你要是拿了它背包里剩余容量就是j - w[i]你在这个剩余空间里能获得的最大价值是前i-1件物品对应的最优解dp[i-1][j - w[i]]再加上这件物品的价值v[i]。于是状态转移方程水到渠成dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])就这么一个看似平平无奇的式子里面蕴含了DP的全部精髓它是在“不拿”和“拿”这两种决策里取最大值而“拿”这一步又依赖于一个子问题的最优解。2.2 用手填一张表胜过看十篇博客看图不如画图讲一万遍不如手搓一遍。假设现在有三个物品物品重量价值A23B34C45背包总容量是7。我们把这个二维DP表一行一行地填出来。初始化当i0时没有物品可选不管容量多少价值都是0所以dp[0][j] 0j从0到7。现在开始处理第一件物品A重量2价值3j 2时装不下不拿价值0。j 2时可以选择拿价值0前0件的价值 3 3。所以第1行从j2开始都是3。再处理第二件物品B重量3价值4j 3时装不下B老老实实继承上一行的值也就是dp[1][j]。j 3时两种选择不拿B沿用dp[1][3]3拿B必须给B腾出3的空间剩下容量为0dp[1][0] 4 4。取最大值dp[2][3] 4。j 4时不拿B是dp[1][4]3拿B的话dp[1][1] 4 0 4 4。所以dp[2][4] 4。j 5时这是关键的一格不拿B是dp[1][5]3拿B的话dp[1][2] 4 3 4 7。哇一下子变成7了因为容量足够先把A装进去再装B。后面的j6、7都是拿B的策略更优价值一直是7。最后处理第三件物品C重量4价值5j 4时装不下C全是继承上一行的值。j 4时不拿C是dp[2][4]4拿C则dp[2][0] 5 5。所以dp[3][4] 5。j 6时不拿C是dp[2][6]7拿C则dp[2][2] 5 3 5 8。所以dp[3][6] 8。j 7时不拿C是dp[2][7]7拿C则dp[2][3] 5 4 5 9。所以dp[3][7] 9。填完之后dp[3][7] 9就是整个问题的最优解。回头再去看那个转移方程是不是感觉像老朋友了这张表里的每个数字都是被“憋”出来的它们不是天上掉下来的公式而是一步一步决策的结果。2.3 一维数组的秘密为什么要倒序遍历上面用二维数组理解起来很美好但空间复杂度是O(N * V)。当N和V都是上万时内存直接爆掉。这时候就该让一维数组出场了。如果仔细看上面的转移方程你会发现dp[i][j]只和dp[i-1][...]有关和更往前的行完全没关系。这意味着我们可以只用一个一维数组dp[j]然后原地更新它。关键在于更新的时候必须倒着遍历容量。来想想为什么。假设正序遍历当我们算到dp[5]的时候它需要用到的是上一行的dp[3]。但问题在于如果同一轮循环里我们先更新了dp[3]因为正序遍历3 5它已经被更新过了那dp[5]拿到的dp[3]就是这一轮的“新值”而这个新值里可能已经包含了当前这个物品这就导致同一个物品被装了两次完全违背了01背包“每件物品只能拿一次”的设定。如果倒序遍历呢我们从jV一直算到jw[i]算dp[j]的时候需要用到的dp[j - w[i]]因为它的下标比j小而我们是倒着走的这个下标更小的值在这一轮循环里还没有被更新过拿到的还是上一轮的旧值。这正好符合转移方程的要求这是一个极其关键、又极其容易犯错的地方。我当年第一次学一维优化时想破脑袋也没想明白后来自己动手验证了一遍正序遍历的结果发现物品被重复选了才彻底懂了。下面是01背包的完整实现以Python为例代码极简但信息密度极高def knapsack_01(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): # 关键点for循环从大到小 for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]注意倒序遍历的终点是weights[i]这意味着j小于当前物品重量时更新没有意义装不下。这个细节能帮你省掉一小部分无效操作在大数据量时积少成多。3. 从01背包出发一口气搞定完全背包和多重背包说实话理解了01背包学习完全背包和多重背包的曲线会瞬间平缓很多。它们之间的差别往往只是一两行代码的变化但背后的逻辑完全不一样。3.1 完全背包无限拿反而更简单完全背包的问题描述是每件物品可以取无数次。场景也很常见比如你有无限量的同样零件怎么装价值最大或者有无限张的优惠券怎么组合使用最划算。如果你把完全背包的二维转移方程写出来会发现它变成了dp[i][j] max(dp[i-1][j], dp[i][j - w[i]] v[i])。注意第二个参数里是dp[i][...]而不是dp[i-1][...]。意思就是当我决定拿这个物品时我还可以继续考虑在同一轮循环里再拿它一次因为它的数量是无限的。到了代码层面这个变化就更有意思了。在01背包的一维优化里我们为了防止重复拿选择倒序遍历而完全背包恰恰相反它在设计上就允许你重复拿所以你可以正序遍历容量def knapsack_complete(weights, values, capacity): n len(weights) dp [0] * (capacity 1) for i in range(n): for j in range(weights[i], capacity 1): # 正序 dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]看到没有唯一的区别就是range的方向变了。但这个变化恰好就是“重复拿”和“不能重复拿”的灵魂区分。我见过很多人在面试时栽在这一行上被面试官一问“为什么”就支支吾吾说不清楚。你只要脑子里能想到“正序会覆盖旧值让同一物品被选中多次”这个画面就永远忘不了。3.2 多重背包二进制拆分一个很骚的优化多重背包则是01背包的另一个变种每个物品有数量上限。比如苹果有3个梨有5个。最粗暴的办法是把每个物品复制成好多个独立的01背包物品比如3个苹果就当成3个不同的物品反正它们重量、价值一样数量也正好对应上。这样做的复杂度是O(N * count * V)当count很大时明显就顶不住了。这里有个经典的优化思路叫二进制拆分。核心思想是任何一个正整数都可以用若干个2的幂次方比如1、2、4、8...和最后一个余数来表示。举个例子如果某样物品有13个。朴素拆分是把13个当成13个01物品。二进制拆分则把13拆成1、2、4、6注意这里最后一个不是8而是13-1-2-46。因为1、2、4能组合出0到7的所有数再加上一个6就能组合出0到13的所有数量需求。这样一来13个物品就变成了4个“虚拟物品组”。数量为1的组要么拿要么不拿数量为2的组要么拿要么不拿……通过拿不拿这些组可以拼出0到13的任何数量完全等价于原来的13个独立物品。复杂度一下就降到了O(N * log(count) * V)。这在竞赛场景里是救命的优化手段。def knapsack_multiple(weights, values, counts, capacity): # 先把多重背包转换成01背包 w [] v [] for i in range(len(weights)): cnt counts[i] k 1 while cnt k: w.append(weights[i] * k) v.append(values[i] * k) cnt - k k 1 if cnt 0: w.append(weights[i] * cnt) v.append(values[i] * cnt) # 然后直接用01背包的函数 return knapsack_01(w, v, capacity)思路点拨这段代码先做二进制拆分的预处理生成新的重量列表和价值列表然后调用标准的01背包解法。理解二进制拆分的“为什么”比背代码重要一百倍。这里的核心是任何数量限制都能被拆成若干个“可组合出任意数量”的组这些组在01背包的框架下正好能模拟原来的多重选择。3.3 三种背包的核心差异速查为了让你一眼看清三种背包的异同我把它们的关键点整理成一张表类型每件物品拿取数量一维代码遍历顺序核心代码差异01背包最多1次倒序for j in range(capacity, weight, -1)完全背包无限次正序for j in range(weight, capacity1)多重背包有限次倒序 二进制拆分先拆分再套01背包模板这张表是面试前必须刻在脑子里的。很多时候面试官不会直接说“来解个01背包”而是包装成“你有若干种不同价值的股票怎么配置才能在一定资金限制下收益最大”你得能快速识别出这其实是哪种背包然后对症下药。4. 背包问题的进阶变种从“入门”到“入魔”学会了三种基础背包后面的路一下子开阔了起来。背包问题之所以能成为算法竞赛的常青树就是因为它能结合不同的条件产生海量变种。这里我挑几个最常出现的帮你把思路延展开。4.1 恰好装满 vs 不超过容量一个初始化的坑前面我们一直假设“不超过容量V”。但有的题目会明确问你“恰好装满背包时最大价值是多少”。这个情况下初始化逻辑必须改。不超过容量dp数组全部初始化为0表示什么都不装价值为0。恰好装满dp[0]0其余都初始化为-inf负无穷。为什么因为“恰好装满”要求状态必须由一条有效的路径拼出来。如果你什么都装根本没有“装满”这个状态所以只有容量为0的状态是合法的。如果一个状态dp[j]是负无穷说明没有任何一种组合可以恰好凑出重量j那它就不能作为转移的基础。这就像你盖房子只能从已经打好的地基上接着盖凭空悬浮的楼层是不存在的。这个初始化技巧极其常见别小看它。我见过无数人在LeetCode上栽在“零钱兑换”的变体题上根子就是没搞懂负无穷初始化的意义。4.2 二维费用背包再加一个约束也是一张表有些问题里每个物品不仅占重量还占体积。背包也不是单纯一个而是有容量和体积双重上限。这时候状态定义就要升级为dp[j][k]表示“在容量j、体积k限制下能获得的最大价值”转移方程则变成dp[j][k] max(dp[j][k], dp[j - weight][k - volume] value)代码实现上只需要在原来一维数组的基础上再加一层循环def knapsack_2d(weights, volumes, values, capacity, total_volume): dp [[0] * (total_volume 1) for _ in range(capacity 1)] for i in range(len(weights)): for j in range(capacity, weights[i] - 1, -1): for k in range(total_volume, volumes[i] - 1, -1): # 依然是倒序 dp[j][k] max(dp[j][k], dp[j - weights[i]][k - volumes[i]] values[i]) return dp[capacity][total_volume]二维背包的核心逻辑没有变只是状态空间多了一维。它特别适合解决多约束资源分配类的实际问题比如预算和人力都受限的项目组合优化。4.3 分组背包每组只能挑一个分组背包说的是若干组物品每组里有若干个不同的选择但你只能从每组里挑一个或者一个都不挑。比如选择手机时苹果生态、安卓生态你只能二选一不能两套系统一起买。它的转移逻辑是先遍历组再遍历容量倒序最后遍历组内物品。注意这个顺序极其严格错一点都不对。因为如果你把容量循环放在最外层会导致同一组里的多个物品被视作可以同时选择的那就完全变味了。def knapsack_group(groups, capacity): # groups 是列表的列表每个子列表里存 [(weight, value), ...] dp [0] * (capacity 1) for group in groups: for j in range(capacity, 0, -1): # 先容量 for w, v in group: # 再组内物品 if j w: dp[j] max(dp[j], dp[j - w] v) return dp[capacity]分清楚“先容量后组内”和“先组内后容量”的区别是理解分组背包的钥匙。前者保证一组内最多选一个后者会变成组内物品可以同时选彻底跑偏。4.4 求方案数把“最大”改成“累加”背包问题还有一种超常见变种是问你有多少种不同的装法能凑出价值或重量目标。比如LeetCode 494题“目标和”就是典型的01背包求方案数。这种题的DP数组不再存“最大价值”而是存“方案数量”。转移方程也从max变成了加法dp[j] dp[j] dp[j - w[i]]含义是不拿这个物品的方案数dp[j]加上拿这个物品的方案数dp[j - w[i]]加起来就是总方案数。注意这里dp[0]要初始化为1因为“什么都不选”本身就是一种方案是所有累加的起点。这个和恰好装满里dp[0]0的思想是相反的别搞混。4.5 打印具体选择了哪些物品有时候你不仅需要最大价值还需要知道具体拿了哪些物品。这需要你开一个choice[i][j]数组记录在dp[i][j]这个状态是选择了“拿”还是“不拿”第i件物品。等整个DP跑完从最后一个状态往前回溯。# 在01背包转移时记录选择 choice [[False] * (capacity 1) for _ in range(n)] for i in range(n): for j in range(capacity, weights[i] - 1, -1): if dp[j - weights[i]] values[i] dp[j]: dp[j] dp[j - weights[i]] values[i] choice[i][j] True # 回溯打印 result [] j capacity for i in range(n - 1, -1, -1): if choice[i][j]: result.append(i) j - weights[i]这个技巧在处理“请输出最优方案”这类题目时是必备的。注意回溯时要从后往前推因为高维状态依赖于低维状态的决策记录。5. 防坑指南与实际问题识别技巧写了5个章节的代码现在该说说那些让人挠头的坑了。背包问题的代码不长但恰恰因为短每个细节都被放大了。任何一个小错误都会让你的输出像一个随机生成的数字而你根本不知道问题出在哪。5.1 常见问题速查表照着对一遍我把这些年踩过、也见过别人踩的坑整理成一张表格每一条后面都附上排查思路。你在AC不了题目的时候按这张表逐行查基本能解决九成的问题。症状可能原因修复思路结果偏大不是一个合法的装入方案01背包写成了正序遍历物品被重复使用把容量循环改成倒序从capacity到weight结果偏小且随着容量增大不递增物品的重量为0但遍历时j提前跳出循环检查j的起点处理weight为0的边界所有结果都是0价值数组读取错误或者物品重量远大于容量打印weights和values检查输入解析恰好装满问题时结果全是负无穷初始化没把dp[0]设为0其他设为-inf重新审视题目要求调整初始化逻辑内存溢出二维数组太大考虑使用一维数组优化空间复杂度分组背包结果异常循环顺序写错组内物品被同时选上强制先组、再容量、再组内物品记住一个排查思路小数据量时打印DP表格或者手动模拟一遍。这比盯着代码空想一百遍都管用。我写DP题卡住时从来没有一次是靠冥想解出来的。5.2 从实际场景中识别出“背包问题”这是一项很关键的应试技能。面试官不会说“这是一道背包题”他会说“公司有N个候选人每个候选人期望薪资不同产出不同招聘预算有限怎么选收益最大”。这个场景里候选人就是物品期望薪资就是重量产出就是价值招聘预算就是容量。这就是一个标准的01背包。另一个常见场景你有m种硬币每种硬币面额不同数量无限请问凑出总金额n最少需要几枚硬币这是一个完全背包问题但要求的不再是最大值而是最小值。转移方程就变成dp[j] min(dp[j], dp[j - coin] 1)初始化的思路也变了dp[0]0其他初始化为无穷大表示无法凑出。识别题型的能力比会背模板值钱太多。判断一个问题是不是背包就抓手两个特征是否存在有限资源限制容量是否每个选择都有独立的成本与收益重量与价值。这两个特征一出现就能往背包上靠。5.3 性能估算你的算法跑得动吗最后聊聊复杂度。01背包的时间复杂度是O(N * V)空间复杂度优化后是O(V)。这里的N是物品数量V是容量大小。很多人忽略了一个事如果V特别大比如10^9那O(N*V)直接就是天文数字该怎么优化这时候有两个常见方向压缩状态空间如果重量和价值有规律比如所有重量都是某个数的倍数可以把容量缩小一个量级。换成其他思路如果N很小而V很大可以考虑用搜索/折半枚举来替代DP或者换用别的算法框架。竞赛题里经常有这种“V很大但N很小”的陷阱。你要是看不出来一股脑套背包模板那就是在给评测机送人头。在实际工程里也一样内存和时间总有一个要先被牺牲你得提前想清楚。6. 从“看懂题解”到“独立AC”的实战路线我知道很多人看这篇文章的时候手上的题单已经躺了一堆背包题了。这里我根据自己的经历给出一条稳妥的刷题路线你来对照着走就不会慌。6.1 先刷出感觉的入门清单入门阶段别贪多先确保这几类题目能独立做出来纯01背包模板题一维和二维都要手撸一遍纯完全背包模板题正逆序对比吃透多重背包模板题会套二进制拆分恰好装满类的变种题01背包求方案数每道题做完之后干一件事把代码里的正逆序改反看看结果如何变化。这个对比实验比做十道新题都管用。只有亲手制造出bug再亲手解决它你对“为什么倒序”的理解才算真正落地。6.2 进阶挑战混合背包与依赖背包等你基础题刷得差不多了就可以碰一些更复杂的组合题了混合背包同时存在01、完全、多重三种物品。解法是按物品种类分别处理遇到不同类别就用不同的遍历方式。有依赖的背包比如“金明的预算方案”买附件之前必须先买主件。解决思路是把“主件和它的一组附件”看成一个物品组然后按分组背包来跑。二维费用背包重量体积双重限制相当于多套一层循环。这些题目之所以值得刷是因为它们强迫你把底层原理融会贯通而不是浮在表面的“背模板”。6.3 面试场景下的脑内推演如果你是为了面试准备最后再来一个加分项在脑子里把“为什么要倒序遍历”“为什么初始化为-inf”“为什么分组背包的循环顺序不能乱”这些问题用大白话讲给自己听一遍。面试官通常看重的不是你能不能AC而是你遇到问题的思考过程。你把背包的逻辑讲得滔滔不绝比闷声敲出一个AC代码更能打动对方。我见过太多候选人能写出正确答案但被问一句“如果物品重量是浮点数怎么办”答案是容量做离散化处理就当场卡壳。这种追问考察的就是你对模型本质的理解深度。7. 写在最后的个人经验背包问题学到这里其实你已经掌握了动态规划最核心的心法把大问题拆成小问题记录小问题的答案再用它们拼成大问题的答案。很多人觉得DP玄学其实只是因为填表的样本量还不够只要亲手填过几张大表那种“啊哈”的顿悟感迟早会来。最后再分享一个小技巧手边常备纸笔遇到任何DP题目先别碰键盘用5分钟把状态定义、转移方程写在纸上确认没有逻辑漏洞再动手写代码。这5分钟能帮你省下后面调试的50分钟。背包不是终点它只是一个起点。等你哪天回头看这篇文章能一眼看出“这题是在考01背包的一维优化”时说明你已经真正上道了。继续保持这个状态动态规划这片森林你会越走越清晰。