动态规划入门：从01背包到多重背包的核心思想与代码实现

1. 项目概述从背包问题看动态规划的核心脉络最近在整理自己的算法刷题日志翻到了第37和38天连续啃下的硬骨头——01背包和多重背包问题。这两个问题可以说是动态规划领域的“必修课”也是面试中检验候选人基本功的经典考题。很多朋友一听到“动态规划”就觉得头大状态转移方程、最优子结构这些概念听起来很玄乎。但以我个人的经验来看背包问题恰恰是理解动态规划思想最直观、也最有效的切入点。它不像有些题目那样抽象而是有一个非常具体的物理场景给你一个容量有限的背包和一堆各有重量和价值的物品你怎么装才能让背包里的总价值最大这个场景本身就能帮助我们具象化地理解“状态”和“选择”。我之所以把这两天的日志单独拿出来复盘是因为它们代表了动态规划中两种基础但至关重要的模型。01背包是“选与不选”的二元决策奠定了背包问题乃至许多DP问题的基石而多重背包则引入了“物品数量”这个新维度是向更复杂问题如混合背包、二维费用背包过渡的关键阶梯。弄懂这两个问题不仅能让你在力扣、牛客上解决一大批标签为“背包”的题目更能帮你建立起用动态规划分解复杂问题的思维框架。无论你是正在准备求职面试的学生还是希望巩固算法基础的在职工程师跟着我的日志走一遍保证你会有“原来如此”的豁然开朗感。2. 核心思路拆解为什么背包问题适合用动态规划在深入代码之前我们必须先搞清楚一个根本问题为什么背包问题尤其是01背包和多重背包天然适合用动态规划来解决这得从动态规划能有效解决问题的两个核心特征说起最优子结构和重叠子问题。2.1 最优子结构当前最优解依赖于子问题最优解背包问题的最优子结构非常明显。假设我们有一个容量为C的背包面对前i件物品。对于第i件物品我们只有两种选择01背包或有限种选择多重背包把它放进背包或者不放进背包。如果我们决定放进去那么问题就转化为在背包剩余容量为C - weight[i]的前提下从前i-1件物品中能获取的最大价值是多少然后再加上当前物品的价值value[i]。如果我们决定不放那么问题就转化为在背包容量仍为C的前提下从前i-1件物品中能获取的最大价值是多少关键在于无论我们做哪种选择我们都在求解一个规模更小物品数量更少的“子背包问题”。并且整个问题的最优解装前i件物品到容量C背包的最大价值必然由这些子问题的最优解组合而成。这就是“最优子结构”——大问题的最优解可以通过其子问题的最优解推导出来。动态规划正是利用这个特性通过解决所有子问题来构建原问题的解。2.2 重叠子问题避免重复计算的钥匙如果我们用最朴素的递归回溯思路去解决背包问题会写出类似这样的伪代码def knapsack(i, c): # 考虑前i件物品剩余容量c if i 0 or c 0: return 0 if weight[i] c: # 放不下 return knapsack(i-1, c) else: # 选择不放或放取最大值 return max(knapsack(i-1, c), knapsack(i-1, c-weight[i]) value[i])这个递归树会指数级爆炸因为knapsack(i-1, c)和knapsack(i-1, c-weight[i])这样的子问题会被重复计算无数次。例如在计算knapsack(5, 10)时可能会计算knapsack(3, 7)在计算knapsack(4, 10)时可能又会计算knapsack(3, 7)。这就是“重叠子问题”。动态规划的精妙之处在于它用一个数组通常是二维的dp[i][c]把这些子问题的解都“备忘录”下来。当需要某个子问题的解时先去表里查如果已经计算过就直接返回避免重复计算。这样就把指数级的时间复杂度降到了多项式级对于01背包是O(N*C)。从递归到动态规划本质上是一种“用空间换时间”的策略而背包问题是体现这一策略优越性的绝佳例子。3. 01背包问题从二维到一维的降维打击01背包是所有背包问题的源头它的定义非常简单有N件物品和一个容量为C的背包。第i件物品的重量是weight[i]价值是value[i]。每件物品只有一件要么放入背包状态1要么不放入背包状态0。求解将哪些物品装入背包可使总价值最大。3.1 二维DP最直观的理解方式对于初学者我强烈建议从二维动态规划数组开始理解。我们定义dp[i][j]表示考虑前i件物品物品编号从1到i在背包容量为j的情况下可以获取的最大价值。那么状态转移方程就呼之欲出了放不下如果第i件物品的重量weight[i-1]注意代码中通常下标从0开始大于当前背包容量j那么它肯定不能放。此时的最大价值就等于只考虑前i-1件物品、容量为j时的最大价值dp[i][j] dp[i-1][j]。放得下如果第i件物品能放下weight[i-1] j我们面临选择选择不放价值为dp[i-1][j]。选择放价值为dp[i-1][j - weight[i-1]] value[i-1]。意思是先给第i件物品腾出地方看剩下的容量j - weight[i-1]下前i-1件物品能创造的最大价值然后加上当前物品的价值。 我们的目标是总价值最大所以取两者中的最大值dp[i][j] max(dp[i-1][j], dp[i-1][j - weight[i-1]] value[i-1])。初始化时dp[0][j]表示考虑0件物品无论背包容量多大价值都是0。dp[i][0]表示背包容量为0什么也装不下价值也是0。二维DP的代码非常清晰是理解思想的蓝图def knapsack_2d(weight, value, capacity): n len(weight) dp [[0] * (capacity 1) for _ in range(n 1)] for i in range(1, n 1): # 遍历物品 w, v weight[i-1], value[i-1] for j in range(1, capacity 1): # 遍历背包容量 if j w: # 当前背包容量装不下第i件物品 dp[i][j] dp[i-1][j] else: # 能装下进行决策 dp[i][j] max(dp[i-1][j], dp[i-1][j - w] v) return dp[n][capacity]实操心得在面试白板 coding 时如果时间允许可以先写出二维DP并解释清楚状态定义和转移方程。这能向面试官展示你扎实的基础理解而不是死记硬背一维优化。3.2 一维DP滚动数组空间优化的艺术二维DP的空间复杂度是O(N*C)。观察状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j - w] v)你会发现当前状态dp[i][j]只依赖于上一行dp[i-1][...]的数据。也就是说我们完全不需要保存整个二维表格只需要一个一维数组dp[j]来代表“当前考虑物品时不同容量下的最大价值”即可。但这里有一个至关重要的细节遍历背包容量j时必须从大到小逆序遍历。 为什么我们来看如果正序遍历会发生什么。假设weight[0]1, value[0]15容量C4。初始化dp [0,0,0,0,0]。正序遍历j从1到4j1:dp[1] max(dp[1], dp[0]15) max(0, 015)15。此时dp [0,15,0,0,0]。j2:dp[2] max(dp[2], dp[1]15) max(0, 1515)30。这里就出问题了dp[1]是15意味着我们在容量为1时已经放了物品0价值15。现在计算dp[2]时又用到了dp[1]并加上了物品0的价值相当于物品0被放了两次这违背了01背包“每个物品只能用一次”的规则。逆序遍历从C到weight[i]可以完美避免这个问题。因为dp[j - weight[i]]总是在dp[j]之前被更新j从大到小j-weight[i]更小而它保存的是“上一轮”即考虑前i-1件物品时的状态保证了物品不会被重复添加。一维DP的代码更加简洁高效def knapsack_1d(weight, value, capacity): n len(weight) dp [0] * (capacity 1) for i in range(n): # 遍历物品 w, v weight[i], value[i] for j in range(capacity, w - 1, -1): # 逆序遍历背包容量 dp[j] max(dp[j], dp[j - w] v) return dp[capacity]避坑指南“一维DP必须逆序遍历背包容量”是01背包最经典的坑点也是面试高频考点。务必理解其背后的原因——防止同一物品被多次使用。你可以把它记成“01背包一维解容量倒着走”。4. 多重背包问题当物品不再是“唯一”多重背包是01背包的自然延伸它放宽了一个限制第i种物品最多有s[i]件而不是只有一件。这意味着对于每种物品我们的选择从“放(1)或不放(0)”变成了“放0件、放1件、...、放s[i]件”。这立刻带来了新的挑战。4.1 朴素解法转化为01背包最直观的思路是把多重背包“摊平”成01背包。如果一种物品有s件我就把它看成是s个完全相同的、独立的01背包物品。然后直接套用01背包的解法。代码实现很简单就是在遍历物品时内部再套一个循环遍历物品的个数k(从1到s[i])并且要保证k * weight[i] j。def multi_knapsack_naive(weight, value, count, capacity): dp [0] * (capacity 1) n len(weight) for i in range(n): # 遍历物品种类 for j in range(capacity, -1, -1): # 逆序遍历背包容量 # k代表当前准备放入几件物品i for k in range(1, count[i] 1): if j k * weight[i]: dp[j] max(dp[j], dp[j - k * weight[i]] k * value[i]) return dp[capacity]这个解法的时间复杂度是O(C * Σs[i])其中Σs[i]是所有物品的数量总和。如果某种物品有1000件容量也很大这个三层循环会非常慢容易超时。4.2 二进制优化优雅的降维打击如何优化核心思想是我们真的需要把s件物品拆成s个独立的“1”吗不一定。比如数字7我们可以用1、2、4这三个数组合出来1247。同理对于s件物品我们可以将其拆分成若干“份”每份的数量是1, 2, 4, ..., 2^(k-1), s - (2^k -1)使得这些份数通过组合可以表示出0到s之间的任何取件数。这样我们就把s件物品拆成了大约log₂(s)个“新物品”然后对这些新物品做01背包。为什么这样是可行的因为对于多重背包我们在决策时关心的不是“第几件物品”而是“这种物品我最终放了几件”。只要我们能组合出所有可能的件数0到s那么最优解一定包含在其中。二进制拆分用对数级别的物品数覆盖了线性级别的可能性是典型的“空间换时间”或“信息压缩”思想。优化后的代码分为两步二进制拆分遍历每种物品将其数量s按二进制规则拆分成新的重量和价值。01背包求解对拆分后得到的新物品集合直接运行01背包一维算法。def multi_knapsack_binary(weight, value, count, capacity): # 第一步二进制拆分得到新的物品列表 new_weight [] new_value [] for i in range(len(weight)): s count[i] k 1 while k s: new_weight.append(k * weight[i]) new_value.append(k * value[i]) s - k k * 2 if s 0: # 剩余的部分 new_weight.append(s * weight[i]) new_value.append(s * value[i]) # 第二步对拆分后的物品做01背包 dp [0] * (capacity 1) for i in range(len(new_weight)): w, v new_weight[i], new_value[i] for j in range(capacity, w - 1, -1): dp[j] max(dp[j], dp[j - w] v) return dp[capacity]经过二进制优化时间复杂度从O(C * Σs[i])降低到了O(C * Σlog s[i])这是一个巨大的提升足以应对大多数题目。经验之谈在面试或竞赛中遇到多重背包问题除非数据量特别小否则直接上二进制优化是更稳妥的做法。向面试官解释清楚二进制优化的原理用2的幂次组合表示任意数能很好地体现你的算法优化能力。5. 核心细节与变种问题实战理解了01背包和多重背包的基础模板我们才算刚刚入门。真正的挑战在于识别问题变种并将其转化为背包模型。下面结合我刷题时遇到的几个典型例子拆解一下解题思路。5.1 问题转化识别背包模型的“马甲”很多题目不会直接告诉你这是背包问题你需要自己提炼出“容量”和“物品”。经典例题分割等和子集LeetCode 416给你一个只包含正整数的非空数组nums请你判断是否可以将这个数组分割成两个子集使得两个子集的元素和相等。转化思路计算数组总和sum。如果sum是奇数直接返回false因为无法平分。问题转化为能否从数组中选出一部分数使得它们的和等于target sum / 2。识别模型数组中的每个数就是一个“物品”其“重量”和“价值”都是数值本身。背包的“容量”就是target。我们需要判断是否存在一种“装法”恰好装满容量为target的背包。这本质上是一个01背包的“是否存在”问题而不是“最大价值”问题。我们可以定义dp[j]为容量为j的背包能否被恰好装满布尔值。状态转移对于数字num如果j num那么dp[j] dp[j] or dp[j - num]。意思是当前容量j能被装满要么是之前就能装满不选num要么是装了num之后剩下的容量j-num能被装满。初始化dp[0] true表示容量为0的背包默认就是满的不装任何物品。经典例题零钱兑换 IILeetCode 518给你一个整数数组coins表示不同面额的硬币另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。转化思路硬币面额是“物品的重量”每种硬币有无限个——这明显是完全背包问题多重背包的特例数量无限。背包“容量”是amount。要求的是“组合数”而不是最大价值。我们定义dp[j]为凑成总金额j的硬币组合数。关键区别遍历顺序。在求组合数时必须先遍历物品硬币再遍历背包容量。为什么因为这样可以保证在考虑一种面额时不会出现顺序不同的重复组合。例如amount5, coins[1,2,5]组合[1,2,2]和[2,1,2]被视为同一种。先遍历硬币意味着我们固定了硬币种类的考虑顺序从而避免了排列。状态转移dp[j] dp[j - coin]。初始化dp[0] 1表示凑成金额0有一种组合什么都不选。排查技巧当你怀疑一道题是背包问题时问自己三个问题(1) 有没有一个限制的“总量”容量(2) 有没有可选择的“单元”物品(3) 每个“单元”是否有“消耗”重量和“收益”价值如果答案是肯定的那么八九不离十。再根据物品能否重复选判断是01背包、完全背包还是多重背包。5.2 初始化与遍历顺序的陷阱这是背包问题最容易出错的两个地方。初始化求最大价值/最小重量通常dp数组初始化为0。如果题目要求恰好装满背包那么除了dp[0]0其他dp[j]应初始化为一个“不可能”的值如-inf对于求最大值inf对于求最小值表示无法恰好装满。求方案数dp[0]通常初始化为1代表一种方案什么都不选其他为0。遍历顺序01背包一维DP必须先遍历物品再逆序遍历背包容量。完全背包求最大价值/最小重量一维DP先遍历物品再正序遍历背包容量。求组合数先遍历物品再正序遍历背包容量保证是组合。求排列数先遍历背包容量再遍历物品考虑顺序。多重背包先进行二进制拆分然后当作01背包处理先物品后逆序容量。我习惯用一个表格来总结方便记忆问题类型遍历物品/容量顺序 (一维DP)容量遍历方向典型应用01背包先物品后容量逆序最大价值、恰好装满、方案数需注意初始化完全背包 (最大价值)先物品后容量正序零钱兑换最小硬币数、单词拆分完全背包 (组合数)先物品后容量正序零钱兑换 II组合数完全背包 (排列数)先容量后物品正序组合总和 IV排列数多重背包二进制拆分后同01背包逆序有数量限制的物品选择6. 刷题实战与调试心得理论懂了代码写了不代表真的会了。我第37、38天的主要时间其实花在了调试和总结各种边界情况上。分享几个让我“卡壳”后恍然大悟的瞬间。6.1 调试案例为什么我的“恰好装满”方案总是多一个在做“分割等和子集”时我一开始用求最大价值的思路最后判断dp[target] target。但这样无法区分是“恰好装满”还是“价值不超过target”。正确的做法是使用布尔DP或者将初始值设为负无穷对于求最大值只有能从有效的状态转移过来值才会被更新。错误示范# 错误这只是求不超过target的最大值不是能否恰好等于target dp [0] * (target 1) for num in nums: for j in range(target, num-1, -1): dp[j] max(dp[j], dp[j-num] num) return dp[target] target # 这个判断可能为真即使不能恰好装满正确解法布尔DPdp [False] * (target 1) dp[0] True for num in nums: for j in range(target, num-1, -1): dp[j] dp[j] or dp[j - num] # 状态转移 return dp[target]6.2 性能优化当容量太大时怎么办有些题目物品重量和价值都很小但背包容量巨大比如10^9直接O(N*C)的DP会超时或超内存。这时需要转换思路。思路一交换维度。如果总价值范围较小而容量范围很大可以定义dp[i][v]为考虑前i件物品总价值恰好为v时的最小重量。最终答案就是寻找满足dp[n][v] C的最大v。这样复杂度就变成了O(N * Σvalue)可能更优。思路二Meet-in-the-Middle。对于N较小如N40但容量巨大的情况可以将物品分成两半分别枚举每一半所有可能的组合重量价值然后排序后用双指针或二分查找在两部分中寻找最优组合。复杂度约为O(2^(N/2))。6.3 常见“坑点”速查表坑点描述错误原因正确做法一维01背包结果偏大背包容量正序遍历导致物品被重复添加容量必须逆序遍历求组合数时结果包含重复排列遍历顺序是先容量后物品求组合数时应先遍历物品后遍历容量“恰好装满”判断错误使用普通最大价值DP初始化全0使用布尔DP或初始化dp[0]0,dp[其他]-inf多重背包超时使用三层循环的朴素解法使用二进制优化拆分物品数组下标越界遍历容量时边界条件没处理好内层循环条件应为for j in range(C, w-1, -1)初始化值不对导致结果错误根据问题类型最大/最小、方案数初始化错误仔细分析dp[0]的含义方案数通常为1最小值通常为0或inf连续两天聚焦于背包问题感觉像是打通了动态规划的“任督二脉”。最大的收获不是背下了几个模板而是培养了一种“建模”思维面对一个复杂问题如何识别其中的“物品”、“容量”和“价值”如何定义状态如何构建状态之间的转移关系。这种思维可以迁移到很多其他DP问题上比如字符串编辑距离、最长公共子序列等。下次再遇到类似的题目我可能会先停下来画个表格想想这是不是一种变相的“背包”。刷题不是目的通过题目训练这种分解和建模问题的能力才是算法学习带给我们的长期价值。最后一个小建议理解之后一定要自己关掉参考从头到尾手写几遍代码直到能流畅地写出二进制优化这样的关键片段才算真正内化。