写在前面如果你刷过 LeetCode一定对背包问题不陌生。这题看似简单——不就是在容量限制下选东西吗——但变种之多、套路之深足以让无数人在面试现场翻车。我当初学背包问题的时候0/1背包、完全背包、多重背包、分组背包……各种名字看得眼花缭乱完全分不清谁是谁。后来刷多了才发现其实这些变种的核心思想都一样区别只在于遍历顺序和状态转移方程的细微差别。这篇文章我会把背包问题的来龙去脉讲清楚从最基本的 0/1 背包出发逐步扩展到完全背包、多重背包每种都配上完整的 Python 代码和图解。看完这篇面试遇到背包问题你应该能稳如老狗。一、背包问题到底是什么先来看最原始的问题描述你有一个容量为 W 的背包面前有 n 个物品第 i 个物品的重量是 weight[i]价值是 value[i]。每个物品只能选一次问在不超过背包容量的前提下能装入的最大总价值是多少这听起来像不像你平时逛超市购物车就这么大你想买的东西又重又贵怎么挑才能花最少的钱买到最值的东西这就是背包问题的现实原型。但背包问题远不止这一种。根据物品的选取规则不同它可以分成好几种类型选取规则典型题目0/1背包每个物品只能选 0 次或 1 次LeetCode 416、494完全背包每个物品可以选无限次LeetCode 322、518多重背包每个物品有数量限制模板题分组背包每组只能选一个模板题二维费用背包两个限制条件重量体积模板题这篇文章重点讲前两种——0/1背包和完全背包因为面试 90% 的背包题都是这两类的变形。二、0/1 背包最基础的版本2.1 问题分析0/1 背包的核心特点是每个物品只有一件要么选要么不选。不能拆开也不能重复选。假设我们有 4 个物品物品重量价值物品123物品234物品345物品456背包容量 W 8。2.2 状态定义这是 DP 的第一步也是最关键的一步。我们定义dp[i][w]考虑前 i 个物品在背包容量为 w 时能装的最大价值。注意这里的措辞——考虑前 i 个物品不是说一定要选前 i 个而是说只看前 i 个后面的暂时不管。这个定义方式在 DP 里非常常见一定要理解透。2.3 状态转移方程对于第 i 个物品我们有两种选择选择一不选第 i 个物品那最大价值就等于只考虑前 i-1 个物品时的最大价值dp[i][w] dp[i-1][w]选择二选第 i 个物品前提是背包容量够weight[i-1] w。选了之后背包剩余容量变成w - weight[i-1]价值增加value[i-1]。所以dp[i][w] value[i-1] dp[i-1][w - weight[i-1]]两种情况取最大值dp[i][w] max(dp[i-1][w], value[i-1] dp[i-1][w - weight[i-1]])2.4 完整代码二维数组版defknapsack_01(weights,values,W):nlen(weights)# dp[i][w]前i个物品容量w时的最大价值dp[[0]*(W1)for_inrange(n1)]foriinrange(1,n1):# 遍历物品forwinrange(1,W1):# 遍历容量# 先假设不选第i个物品dp[i][w]dp[i-1][w]# 如果容量够看看选了会不会更好ifwweights[i-1]:dp[i][w]max(dp[i][w],values[i-1]dp[i-1][w-weights[i-1]])returndp[n][W]# 测试weights[2,3,4,5]values[3,4,5,6]W8print(knapsack_01(weights,values,W))# 输出: 92.5 DP表格填充过程我用一张图展示一下 dp 表格是怎么被填充的从图上可以看到dp 表格是逐行逐列填充的。每个格子dp[i][w]的值只依赖于它正上方的dp[i-1][w]和左上方的dp[i-1][w-weight[i-1]]。这就是为什么 DP 能避免重复计算——每个子问题只算一次结果被保存下来供后续使用。2.6 空间优化一维数组二维数组虽然直观但空间复杂度是 O(n*W)。观察一下就会发现第 i 行只依赖第 i-1 行前面的行其实用不到了。那能不能只用一维数组呢可以但有个坑遍历容量时必须从后往前为什么因为如果正序遍历当你更新dp[w]的时候dp[w - weight[i]]可能已经被本轮更新过了。这意味着同一个物品被用了两次0/1 背包就变成了完全背包。defknapsack_01_1d(weights,values,W):dp[0]*(W1)foriinrange(len(weights)):# 关键必须从后往前遍历forwinrange(W,weights[i]-1,-1):dp[w]max(dp[w],values[i]dp[w-weights[i]])returndp[W]这个优化把空间复杂度从 O(n*W) 降到了 O(W)面试的时候写出来非常加分。三、完全背包物品可以无限选3.1 问题变化完全背包和 0/1 背包的区别只有一个每个物品可以选无限次。举个例子你有无限张面额为 1、2、5 的硬币要凑出金额 11有多少种方法这就是典型的完全背包问题。3.2 状态转移方程状态定义和 0/1 背包一样dp[i][w]表示前 i 个物品容量 w 时的最大价值。但转移方程稍有不同。因为物品可以无限选选了第 i 个物品之后还可以继续选第 i 个物品dp[i][w] max(dp[i-1][w], value[i-1] dp[i][w - weight[i-1]]) # 注意这里第二项是 dp[i] 而不是 dp[i-1]3.3 一维数组实现完全背包用一维数组优化时遍历顺序是正序这和 0/1 背包正好相反。defknapsack_complete(weights,values,W):dp[0]*(W1)foriinrange(len(weights)):# 关键正序遍历forwinrange(weights[i],W1):dp[w]max(dp[w],values[i]dp[w-weights[i]])returndp[W]3.4 0/1背包 vs 完全背包 核心对比特性0/1背包完全背包物品数量每个只能选1次每个可以选无限次状态转移dp[i-1][w-weight]dp[i][w-weight]一维遍历顺序倒序正序典型题目分割等和子集、目标和零钱兑换、完全平方数记住这个口诀0/1倒序完全正序。这是区分两类背包问题的关键。四、经典题目实战光讲理论没意思我们来刷几道 LeetCode 真题。4.1 分割等和子集LeetCode 416题目给定一个只包含正整数的非空数组判断是否可以将它分割成两个子集使得两个子集的元素和相等。思路数组总和为 sum如果 sum 是奇数肯定分不了。如果 sum 是偶数问题就转化为能否从数组中选出一些数使它们的和等于 sum/2这不就是 0/1 背包吗物品数组中的每个数重量数字本身价值数字本身我们只关心能不能凑出目标值不关心价值最大化背包容量sum/2defcanPartition(nums):totalsum(nums)iftotal%2!0:returnFalsetargettotal//2dp[False]*(target1)dp[0]True# 和为0总是可以达到的什么都不选fornuminnums:# 0/1背包倒序遍历forwinrange(target,num-1,-1):dp[w]dp[w]ordp[w-num]returndp[target]# 测试print(canPartition([1,5,11,5]))# True: [1,5,5] 和 [11]print(canPartition([1,2,3,5]))# False这道题是 0/1 背包的变形但状态从最大价值变成了是否可达用布尔数组代替整数数组。4.2 目标和LeetCode 494题目给定一个非负整数数组和一个目标数 S现在你有两个符号 和 -为数组中的每个整数选择一个符号使得这些整数的和等于目标数 S。求有多少种方法。思路设正数和为 P负数和为 N。则 P - N S且 P N sum。联立得 P (S sum) / 2。问题转化为从数组中选一些数使它们的和等于 P有多少种选法deffindTargetSumWays(nums,target):totalsum(nums)# 如果 target 的绝对值大于 total或者 (target total) 是奇数无解ifabs(target)totalor(targettotal)%2!0:return0P(targettotal)//2dp[0]*(P1)dp[0]1# 和为0有1种方法什么都不选fornuminnums:forwinrange(P,num-1,-1):dp[w]dp[w-num]returndp[P]# 测试print(findTargetSumWays([1,1,1,1,1],3))# 输出: 5这道题也是 0/1 背包但状态从最大价值变成了方案数转移方程从 max 变成了 。4.3 零钱兑换LeetCode 322题目给定不同面额的硬币 coins 和一个总金额 amount编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。思路每种硬币可以无限使用这是完全背包问题。状态dp[w]表示凑出金额 w 所需的最少硬币数。defcoinChange(coins,amount):# dp[w] 表示凑出金额 w 所需的最少硬币数# 初始化为无穷大表示暂时无法凑出dp[float(inf)]*(amount1)dp[0]0# 凑出金额0需要0个硬币forcoinincoins:# 完全背包正序遍历forwinrange(coin,amount1):ifdp[w-coin]!float(inf):dp[w]min(dp[w],dp[w-coin]1)returndp[amount]ifdp[amount]!float(inf)else-1# 测试print(coinChange([1,2,5],11))# 输出: 3 (551)print(coinChange([2],3))# 输出: -1注意初始化dp[0] 0其他设为无穷大。转移方程用 min 而不是 max因为我们要求最少硬币数。4.4 零钱兑换 IILeetCode 518题目给定不同面额的硬币和一个总金额写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。思路完全背包求方案数。但要注意遍历顺序外层遍历硬币内层遍历金额这样才能保证组合不重复。defchange(amount,coins):dp[0]*(amount1)dp[0]1forcoinincoins:forwinrange(coin,amount1):dp[w]dp[w-coin]returndp[amount]# 测试print(change(5,[1,2,5]))# 输出: 4# 组合: [1,1,1,1,1], [1,1,1,2], [1,2,2], [5]五、背包问题的实际应用场景背包问题不是纯理论的东西它在现实中有很多应用场景背包 物品 重量 价值 项目资源分配总工时各个项目项目耗时项目收益投资组合总投资额各种资产投资成本预期收益文件存储存储空间各个文件文件大小重要程度考试复习复习时间各门科目所需天数提分空间广告投放广告预算各个渠道投放成本转化收益理解了背包问题的套路遇到这类资源分配问题你就能很快抽象出 DP 模型。六、常见坑和易错点刷背包题的时候我踩过不少坑这里总结一下6.1 遍历顺序搞反了这是最常见的错误。记住口诀0/1 背包外层物品内层容量倒序遍历完全背包外层物品内层容量正序遍历如果搞反了0/1 背包会变成完全背包完全背包的逻辑也会乱掉。6.2 初始化不对不同的问题初始化方式不同求最大值dp初始化为 0求最小值dp初始化为无穷大dp[0] 0求方案数dp[0] 1其他为 0判断是否可达dp[0] True其他为 False初始化错了后面全白算。6.3 状态定义不清晰dp[w]到底代表什么是恰好装满容量 w 还是不超过容量 w这两个定义在某些题目里结果一样但在另一些题目里比如要求恰好装满就完全不同。读题的时候一定要仔细。6.4 忘了考虑边界情况比如 coinChange 里如果 amount 0应该返回 0 而不是 -1。这些边界情况要在写代码之前就想清楚。七、总结背包问题虽然变种很多但核心思想是一致的定义状态 - 找转移方程 - 确定遍历顺序 - 处理边界条件。记住这几个关键点0/1 背包每个物品只能选一次一维优化时倒序遍历容量完全背包每个物品可以选无限次一维优化时正序遍历容量状态定义决定了转移方程的形式定义之前先在纸上想清楚初始化根据题目要求来求最大、最小、方案数、是否可达各有不同多画图、多手动填表比干想有效得多最后附上一张我整理的背包问题速查表建议收藏问题类型遍历顺序转移方程初始化典型题目0/1背包-最大价值物品外层容量倒序max(dp[w], valdp[w-weight])dp[0]0基础模板0/1背包-是否可达物品外层容量倒序dp[w] dp[w] or dp[w-weight]dp[0]TrueLeetCode 4160/1背包-方案数物品外层容量倒序dp[w] dp[w-weight]dp[0]1LeetCode 494完全背包-最小值物品外层容量正序min(dp[w], dp[w-coin]1)dp[0]0,其余infLeetCode 322完全背包-方案数物品外层容量正序dp[w] dp[w-coin]dp[0]1LeetCode 518背包问题没有捷径就是多刷、多总结。等你把上面这几道题都独立做出来面试遇到背包问题基本就稳了。如果这篇文章对你有帮助欢迎点赞收藏有任何问题可以在评论区留言我会尽量回复。后续会持续更新算法相关的干货内容欢迎关注