背包问题是我线下交流时被问得最多的一块也是面试和竞赛里的常客。01背包、完全背包、多重背包这三兄弟表面上是三个模板本质上是一套思维模型的三个变体。这篇文章我从状态定义开始讲把为什么这么做、为什么优化、为什么循环顺序不一样全部拆开聊一遍配合可以直接复现代码希望能帮你彻底打通这一整套思路。1. 背包问题到底是什么先建立直觉1.1 用生活场景认识三类背包先来说个最常见的场景你有个双肩包容量是V面前有一堆物品每件有自己的重量w和价值v问怎么装能让总价值最大。这就是背包问题的原型。根据“每件物品能拿几次”的规则不同分成了三个经典分支类型物品可拿次数典型场景01背包每件最多拿1次带特产每样只能买一盒完全背包每件可以拿无限次带瓶装水总量不超就行多重背包每件有指定数量上限带苹果家里正好剩5个生活里这类“有限资源下做取舍”的问题遍地都是。投资组合选择项目、服务器分配计算资源、剪辑师决定哪些素材放进成片背后都是一样的模型。学会背包问题等于拿到一套通用优化框架。1.2 为什么暴力搜索不行很多初学者第一反应是枚举把所有组合都算一遍取最大值。但这个思路在数据稍大时立刻崩溃。假设50件物品每件有选和不选两种可能组合数就是2的50次方约等于1126万亿。一台普通家用电脑每秒运算约1亿次光是枚举完这些组合就需要上百天。即使剪枝优化最坏情况依然是指数级。背包问题“物品多一维状态空间翻一倍”的特性让暴力法天然不可行。这也是动态规划登场的原因它不枚举组合而是用“状态”记录子问题的最优解通过状态之间的转移逐步逼近全局最优。1.3 动态规划的核心思路状态与转移动态规划处理背包问题的想法很朴素把“前i件物品在容量j下的最优价值”记下来记为dp[i][j]。然后问自己一个问题——第i件物品到底是拿还是不拿。这就是状态转移的本质当前决策只依赖两个子状态一个是有这件物品时的最优值一个是没有这件物品时的最优值。我们不想知道这件物品到底是谁只想知道达到当前状态的最优代价。这种“只记结果、不记路径”的思想是动态规划的效率来源。但它也带来一个副作用如果题目要求你输出“具体选了哪几件”单靠压缩后的一维数组是做不了的。这个问题我在第5章会专门展开讲。2. 01背包一切背包问题的基础2.1 问题描述与状态定义01背包的标准描述如下有 N 件物品和一个容量为 V 的背包。 第 i 件物品重量为 w[i]价值为 v[i]。 每件物品只能选一次求装入背包的最大总价值。01背包是理解另外两个背包的基石。完全背包、多重背包的优化思路本质上都是在01背包的状态转移方程上做文章。状态定义写成dp[i][j]从前i件物品中选择总重量不超过j时能获得的最大价值。这个定义有两点要注意第一是“从前i件中选择”限制了物品范围第二是“不超过j”允许容量未用完。这两点看似不起眼实际决定了初始化方式。细节在2.5讲。2.2 状态转移方程的推导拿到第i件物品时你只有两个选择。选择一不拿第i件物品。那么问题退化为“从前i-1件物品中容量为j时的最优解”对应dp[i-1][j]。选择二拿第i件物品。那么消耗w[i]的容量获得v[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])这个方程非常对称左边是“不要”的收益右边是“要”的收益。拿还是不拿谁能让我价值更高谁就胜出。注意一个边界条件当j小于w[i]时容量不够装第i件物品此时只能不拿dp[i][j] dp[i-1][j]。代码实现时可以用if判断也可以用倒序遍历的方式自然规避。2.3 二维实现的完整代码先看最直观的二维版本它是理解一切优化的起点。def knapsack_01_2d(N, V, w, v): # dp[i][j] 表示前 i 件物品容量为 j 时的最大价值 dp [[0] * (V 1) for _ in range(N 1)] for i in range(1, N 1): for j in range(0, V 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[i]] v[i]) return dp[N][V]这版代码的时间复杂度是O(NV)空间复杂度是O(NV)。注意N是物品数V是容量不是物品个数和容积的单位两者相乘就是状态总数。实测下来当N和V都在1000左右时二维数组占用内存约为1000乘1000乘8字节约8MB还能接受。当N和V都到5000时内存立刻飙升到200MB很多在线评测系统会直接判超内存。这时候就必须滚动数组优化了。2.4 滚动数组优化为什么容量必须倒序遍历回到二维转移方程观察dp[i][j]到底依赖哪些状态。dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])它只用到了上一行dp[i-1]里的两个值。换句话说dp[i]这行的数据算完之后dp[i-2]及更早的行就再也没有用处了。于是可以把二维数组压缩成一维数组dp[j]表示当前遍历到第i件物品时容量j下的最大价值。每处理完一个物品dp数组自动从“前i-1件的信息”更新为“前i件的信息”。关键点来了更新dp[j]时要看等号右边的dp[j-w[i]]是不是“旧的、还没被当前物品污染过”的值。如果正序遍历j从小到大当你算dp[j]时dp[j-w[i]]可能已经被当前第i件物品更新过了。那么公式的含义就变成了“可以反复拿同一件物品”——这正好是后面要讲的完全背包的语义。如果倒序遍历j从大到小dp[j-w[i]]一定小于j而它在这个循环里还没被更新所以还是上一轮的旧值也就是前i-1件物品的最优解。这样就保证每件物品最多取一次。核心结论一句话01背包用一维数组时必须倒序遍历容量。这是面试里手写代码时最高频的考点也是最容易出bug的地方。改写后的代码def knapsack_01_1d(N, V, w, v): dp [0] * (V 1) for i in range(1, N 1): # 倒序遍历防止一件物品被使用多次 for j in range(V, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[V]注意这里内层循环的范围变成了从V到w[i]小于w[i]的容量装不下当前物品自然不需要更新。相比二维版本省去了if判断代码更简洁。2.5 初始化技巧恰好装满还是不超过容量这是背包问题最容易踩坑的初始化细节很多老手偶尔也会中招。题目描述不同dp数组的初始值就不同。如果题目说“背包不一定装满只要价值最大”dp数组全部初始化为0。因为容量没有用完也是合法状态从一个空背包开始的所有状态价值都是0。如果题目说“恰好装满背包求最大价值”dp[0]初始化为0其余所有dp[j]初始化为负无穷比如-float(inf)。为什么因为只有容量为0且一个物品都不拿时价值才恰好为0其他容量在初始状态下都是“凑不齐”的非法状态用负无穷标记。转移时max自然会把非法状态排除在最优解之外。最终的返回值也有讲究。不是返回dp[V]而是扫描dp[0..V]找最大值。因为“恰好装满”时最优解对应的容量不一定是V可能是小于V的某个值。实测很多新手在这里写出bug输出答案始终偏小。3. 完全背包理解枚举顺序的真正含义3.1 问题描述与朴素思路完全背包的物品规则改成一个词不限次数。每件物品可以选0次、1次、2次……只要总重量不超容量。朴素做法是把完全背包当作01背包处理在01背包的转移里枚举第i件物品到底拿几个。# 朴素三层循环复杂度 O(N * V * K) for i in range(1, N 1): for j in range(0, V 1): for k in range(0, j // w[i] 1): dp[i][j] max(dp[i][j], dp[i-1][j - k * w[i]] k * v[i])这个做法正确但复杂度太高。当每件物品最多可以拿几百次时三层循环直接超时。必须想办法把k循环去掉。3.2 优化一去掉k循环的数学推导观察dp[i][j]的状态转移它枚举k个第i件物品dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i], dp[i-1][j-2w[i]] 2v[i], ...)再写出dp[i][j-w[i]]的转移dp[i][j-w[i]] max(dp[i-1][j-w[i]], dp[i-1][j-2w[i]] v[i], dp[i-1][j-3w[i]] 2*v[i], ...)发现没有dp[i][j-w[i]]加上一个v[i]恰好覆盖了dp[i][j]等号右边从第二项开始的所有内容。于是dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])这个式子的含义是第i件物品可以拿无限次所以如果选择拿一件那么剩余空间的最优解已经可以继续包含第i件物品不需要回到dp[i-1]去。3.3 正序枚举的物理含义上面推导得到的转移方程落到一维数组上就是正序遍历def knapsack_complete(N, V, w, v): dp [0] * (V 1) for i in range(1, N 1): # 正序遍历允许当前物品被重复选取 for j in range(w[i], V 1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[V]对比01背包代码唯一的区别就是内层循环的方向反过来了。这个细节让很多人困惑其实背后的语义非常清晰倒序时dp[j-w[i]]是上一轮的旧值代表“没拿过当前物品”所以每件物品最多一次。正序时dp[j-w[i]]可能已经被当前物品更新过了代表“已经拿过当前物品但还可以再拿”所以物品数量不受限。一句话记忆法01背包问“要不要拿”完全背包问“再拿一件划不划算”。3.4 完全背包完整代码与分析上面代码已经是完整可用版本这里再给一个带路径还原需求时用的二维版本思路帮助理解正序和状态依赖def knapsack_complete_2d(N, V, w, v): dp [[0] * (V 1) for _ in range(N 1)] for i in range(1, N 1): for j in range(0, V 1): if j w[i]: dp[i][j] dp[i-1][j] else: # 注意这里第二项来自 dp[i]不是 dp[i-1] dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i]) return dp[N][V]二维版本中关键区别完全背包的“再拿一件”依赖的是当前行dp[i]01背包依赖的是上一行dp[i-1]。理解这个差异后你就不会再记混一维版本的循环方向了。4. 多重背包多个同款物品怎么处理最高效4.1 问题描述与朴素拆解多重背包在完全背包基础上加了一个限制第i件物品最多能拿s[i]件。最直接的做法是“展开”把第i件物品看成s[i]个独立的物品每个只能拿一次然后跑01背包。比如一件物品限5个就展开成5件一模一样的物品。这个做法在s[i]很小的时候没问题但如果s[i]能达到1万N又是100展开后的“物品数”就是100万跟容量V再乘一下复杂度直接爆炸。那就要二进制拆分。4.2 二进制拆分的核心原理二进制拆分的目的是用尽量少的“组合块”表示0到s之间任意数量的选择。先看一个数学事实用1、2、4、8、16这些2的幂可以组合出0到它们的和之间任意一个整数。比如1、2、4可以表示0到7的所有整数。对数量s按1、2、4、8……依次拆分直到剩下的数不足以组成下一个2的幂就把剩余部分单独作为一个块。def split(s): # 将数量 s 拆成若干块每块作为一件“新物品” k 1 res [] while s 0: take min(k, s) res.append(take) s - take k * 2 return res举个实际例子s10k1取1剩9k2取2剩7k4取4剩3k8此时s3小于8取3剩0拆成1、2、4、3共4块。验证一下用这4个数能组合出0到10之间任意整数吗当然可以。0到7用1、2、4组合8到10分别是7加1、7加2、7加3。拆出来的块数从原来的10块变成4块这就是“对数级”压缩的含义。4.3 二进制拆分为什么能表示任意数量有些读者会问为什么不是拆成s个1拆成s个1当然也能表示任意数量但那是O(s)个块没有优化效果。二进制拆分的巧妙之处在于任意一个整数s都能写成若干个2的幂之和。二进制本来就是计算机表示数字的方式所以这个结论不需要死记理解成“任何数都能用二进制表示”就行。使用这些块跑01背包时选择“拿第1块第4块”就等价于原问题中“拿1件3件4件”。每个块的取舍对应一个二进制位不同组合覆盖0到s的所有取值不多不少。注意拆分是有讲究的最后一个块取的是剩余值本身而不是凑成下一个2的幂。比如s10最后一个块取3而不是8因为取8会超过10。4.4 多重背包完整代码与分析多重背包的完整实现def knapsack_multiple(N, V, w, v, s): dp [0] * (V 1) for i in range(1, N 1): # 二进制拆分当前物品 k 1 cnt s[i] while cnt 0: take min(k, cnt) weight take * w[i] value take * v[i] # 拆出的块当作01背包物品处理倒序遍历 for j in range(V, weight - 1, -1): dp[j] max(dp[j], dp[j - weight] value) cnt - take k * 2 return dp[V]复杂度分析每个物品的s[i]拆成O(log s[i])块总块数为N乘log s再用每块跑一次01背包总复杂度O(V * Σlog s[i])。相比朴素的O(V * Σs[i])提升非常明显。实测一组对比数据N100V10000每个s[i]10000。朴素展开是100万个物品乘1万容量操作数约100亿直接超时。二进制拆分后每个物品约14块总块数约1400操作数约1400万一秒内跑完。5. 高频问题与排查技巧实录5.1 三种背包的枚举顺序速查表我见过太多人在三种背包之间切换时写错循环顺序。直接背下面这张表背包类型物品遍历容量遍历方向含义01背包外层倒序防止物品重复使用完全背包外层正序允许物品重复使用多重背包外层内部先拆块倒序拆块后等价01背包一个记忆技巧需要限制“只能用一次”的容量都倒序允许无限用的容量正序。多重背包拆完后复用了01背包的倒序逻辑顺着这个链条就不会记混。5.2 初始化到底该用0还是负无穷再补充一下这个高频错误。求“最大价值且不用装满”初始化为0求“恰好装满”初始化为负无穷。为什么负无穷不是0反例背包容量为10有一种物品重量为3价值为5。如果初始化全是0“恰好装满”包裹容量10的状态dp[10]会从dp[7]5继承。但dp[7]初始是0表示“什么都没装”却恰好占用7容量这显然是非法状态。它会造成路径虚标让最终答案从不可能的组合里继承价值。负无穷让所有非法状态在max比较中自然消失。这是所有带“恰好”约束的动态规划问题的通用初始化原则不只背包。5.3 数据范围与算法选型判断拿到一道背包题先看数据范围再定方案N和V都在2000以内普通二维01背包足够。N较大、V较大、但物品个数很少考虑压缩状态的其他优化。多重背包中Σs[i]达到1e6以上超过N*V的承受范围必须用二进制拆分。完全背包和01背包是多重背包的特例能处理多重背包的代码往往也能处理前两者只需设置合适的s[i]。容量其实是时间复杂度的主导变量之一。当V达到1e9级别时需要换思路比如按价值作为dp维度或者用贪心加DP的混合策略那种题属于进阶范围基础阶段不用考虑。5.4 需要输出“具体选了哪些物品”怎么办滚动数组优化后dp数组只保留了最后一行无法还原“选了什么”。如果题目要求输出方案必须在转移时记录choice[i][j]表示达到这个状态时第i件物品被拿了几件。完整流程def knapsack_01_with_path(N, V, w, v): dp [[0] * (V 1) for _ in range(N 1)] choice [[0] * (V 1) for _ in range(N 1)] for i in range(1, N 1): for j in range(0, V 1): dp[i][j] dp[i-1][j] if j w[i] and dp[i-1][j-w[i]] v[i] dp[i][j]: dp[i][j] dp[i-1][j-w[i]] v[i] choice[i][j] 1 # 回溯 j V picked [] for i in range(N, 0, -1): if choice[i][j] 1: picked.append(i) j - w[i] return dp[N][V], picked回看时从最后一个物品倒推如果当前状态记录了“这件物品被拿”就把它加进结果序列并扣减对应容量。这里同样要注意倒序回溯跟状态转移的方向相反。5.5 几个真实面试和竞赛中的易错点第一个易错点多重背包二进制拆分时最后一个块如果处理成2的幂可能超出剩余数量。比如s10错误拆成1、2、4、8总和15超过10导致“取到11件”的非法状态。第二个易错点状态转移时忘记判断j-w[i]的边界。用一维数组时通过控制j的起始值可以天然规避用二维数组时别忘了j小于w[i]的分支。第三个易错点完全背包正序枚举时内层j从w[i]开始不是从0开始。从0开始只是多做了无意义的比较不影响正确性但影响性能。第四个易错点下标从0开始还是从1开始。我建议物品和重量都从1开始读入给w[0]和v[0]留空位。这样dp数组和物品索引天然对齐回溯时也顺手。第五个易错点返回值写错。用“恰好装满”的初始化方式时返回dp[V]可能得到负无穷。正确做法是扫描dp[0..V]取最大值。很多人初始化改对了返回值却忘了改实测能让你白白丢掉一个用例。最后分享一个小技巧调试背包问题时优先输出dp数组的末尾几行。一眼就能看出正序和倒序的差异——倒序时dp数组每一行只受上一行影响呈“阶梯式”更新完全背包正序会看到当前物品在多个容量下连续生效。看多了光凭dp数组的模式就能判断写对了没有。这种手感比死记模板有用得多。