背包问题全解析：0/1背包、完全背包与多重背包的递推与优化

背包问题可以说是算法入门阶段绕不开的一座山。不管是刷题准备面试还是参加程序设计竞赛几乎都会碰到它。很多人在网上搜“背包问题”跳出来的第一篇文章往往是0/1背包也就是“背包问题1”这个系列的起点而顺着这个系列往下学自然就会遇到完全背包、多重背包问题这些进阶变种。这篇文章我想用实操的角度把0/1背包、完全背包和多重背包问题的本质一次讲透包括状态转移是怎么来的、循环顺序为什么不能乱改、二进制拆分到底在拆什么以及我在实际调试中踩过的一些坑。1. 把0/1背包吃透从选物品到状态转移1.1 一个场景讲清背包问题在解决什么先看最经典的描述有一个容量为V的背包有n件物品每件物品有自己的重量w[i]和价值v[i]每件物品最多选一次问能装下的最大价值是多少。这就是0/1背包问题也是“背包问题1”里第一道必须搞懂的题。这个模型听起来很“竞赛”但放到现实生活里其实到处都是。比如你出差只有一个20寸登机箱想带几件衣服、相机、充电宝、洗漱包每样东西都有重量和“对旅行的价值”怎么选才能在不超过行李额的前提下让体验最好再比如公司团建有预算几个候选项目各有成本和预期收益怎么组合让总收益最高这些都是典型的0/1背包。关键约束在于“每件物品最多选一次”这个“1”是0/1背包区别于其他背包变种的核心。后面讲完全背包和多重背包本质上都是在这个约束上做修改完全背包是每件物品能选无限次多重背包是每件物品有给定的次数上限。理解了0/1背包后面几种都是在它基础上加一点东西。1.2 为什么暴力枚举走不通很多初学者第一反应是直接枚举所有选与不选的组合不就行了确实n件物品每种物品有选和不选两种情况总共有2^n种组合再逐个算总重量和总价值找出不超过V的最大价值。问题出在规模上。当n20时2^20约100万种组合勉强能跑当n30时2^30已经超过10亿当n100时这个数字大到天文级别普通计算机根本算不完。你可以把这种枚举理解为“把所有可能性都试一遍”而背包问题的决策存在大量重复子问题——前面几件物品的选择方式决定了剩余容量而后面几件物品面对同一个剩余容量时最优选择是一样的。这就像你去超市采购手里剩100元面对同样的商品列表无论你之前是怎么花掉那900元的只要现在手上都是100元你接下来的最优决策就完全相同。暴力枚举把同一个“剩余容量”状态反复计算了很多次而动态规划把每个状态只算一次并保存下来这就是它能大幅降低复杂度的原因。1.3 状态定义和转移方程是怎么想出来的0/1背包的状态定义是所有背包问题的基石。通常定义为dp[i][j]表示前i件物品中挑选若干件放入容量为j的背包能获得的最大价值。这个定义的精髓在于“前i件”和“容量j”这两个维度。前i件把物品逐件引入容量j把背包的所有可能状态枚举出来。接下来考虑第i件物品时只有两种决策不选或者选。不选第i件物品那么问题退化为前i-1件物品在容量j下的最优解也就是dp[i-1][j]。选第i件物品则需要先腾出w[i]的空间那么问题变成前i-1件物品在容量j-w[i]下的最优解再加上第i件物品的价值v[i]也就是dp[i-1][j-w[i]] v[i]。所以转移方程就是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])这里有个细节经常让人困惑为什么选第i件物品时用的是dp[i-1][j-w[i]]而不是dp[i][j-w[i]]因为0/1背包中每件物品只能选一次如果用了dp[i][j-w[i]]那在计算dp[i][j-w[i]]时可能已经把第i件物品放进去了再转移到dp[i][j]就等于把第i件物品用了两次这就不符合“最多选一次”的约束了。提示这个“为什么用i-1”的问题是理解0/1背包和完全背包区别的关键。很多人死记硬背循环方向就是没搞懂这一层。2. 完全背包只改一个循环方向为什么结果就完全不同2.1 完全背包和0/1背包的方程差异完全背包问题把约束改成了“每件物品可以选无限次”。比如背包容量是10某件物品重量是3那它最多能放3件3×39但你也可以选择放1件或2件次数没有上限。如果还用二维dp来写完全背包的转移方程长这样dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])注意看第二个参数0/1背包用的是dp[i-1][j-w[i]]完全背包用的是dp[i][j-w[i]]。为什么因为完全背包允许当前物品被重复选择。计算dp[i][j]时如果已经确定选择第i件物品背包剩余容量j-w[i]在考虑剩余空间还能不能继续放第i件物品时就应该继续使用“当前这层”的状态也就是dp[i][j-w[i]]而这个dp[i][j-w[i]]本身已经包含了可能再次选择第i件物品的结果。如果完全背包还用dp[i-1]那就等于把第i件物品用完一次就“划掉”了没法实现无限次使用的效果。从二维方程到一维滚动数组这个区别就体现在内层循环的方向上。2.2 正序与逆序的底层逻辑一维滚动数组下0/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])完全背包的内层循环却要正着枚举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])这两个方向有什么区别关键在一维数组的“覆盖时机”上。0/1背包倒着枚举时计算dp[j]要用到dp[j-w[i]]而j-w[i]一定小于j。由于j是从大到小遍历dp[j-w[i]]在本轮还没有被更新过它保存的仍然是上一轮也就是前i-1件物品的结果。这正好对应了方程里的dp[i-1][j-w[i]]。完全背包正着枚举时计算dp[j]用的dp[j-w[i]]因为j从小到大遍历j-w[i]小于j所以它在本轮已经被更新过了。这个被更新过的值可能已经包含了当前物品被多次选择的情况正好对应了方程里的dp[i][j-w[i]]。用一个生活化类比把dp数组想成一面记录结果的墙0/1背包是从右往左填每次参考的左边格子还没有被今天的更新“污染”完全背包是从左往右填参考的左边格子已经是今天更新过的结果信息可以往前传递实现无限复用。2.3 初始化细节恰好装满和最多能装是两回事背包问题里初始化往往是“微妙错误”的高发区。最典型的是“恰好装满背包”和“最多能装多少”两种问法的区别。如果题目问的是“在不超过背包容量的前提下最多能装多少价值”那么dp数组全部初始化为0即可。因为容量为0的背包不管在哪个阶段价值都是0而其他容量即使一件物品都装不下价值也是0这个0代表“无法达到该状态但该状态本身合法”。如果题目问的是“恰好装满背包时能装的最大价值”初始化就完全不同。这时候dp[0] 0而dp[1]到dp[V]应初始化为负无穷比如-10^9。为什么因为只有容量为0的背包是“恰好装满”的初始合法状态其他容量用0初始化会让人误以为“不装任何物品”也是一种合法装满方式但实际上容量不为0却一件没装根本不是恰好装满。用负无穷标记这些状态为“不可达”后续转移时如果某个状态始终不可达它的值就会一直保持负无穷最后判断如果dp[V]仍为负无穷说明无法恰好装满。注意很多题目会把“恰好装满”和“不超过容量”混着出读题时一定要先确认。我实战中因为没注意这个问题输出少了或者多了都是常态。3. 多重背包问题拆解、优化与复杂度控制3.1 朴素拆解法为什么容易超时多重背包问题可以描述为有n种物品每种物品有数量上限c[i]重量w[i]价值v[i]在背包容量V内求最大价值。最直接的想法是把第i种物品的c[i]件一个个拆开当作c[i]个独立的0/1背包物品来处理。比如某物品有13件就拆成13件重量相同、价值相同的物品然后套用0/1背包的解法。这个思路完全正确但代价很大。假设n100每种物品平均数量是100那拆出来就是10000件物品再乘以背包容量V复杂度可能直接飙到10^7甚至更高。如果n1000每种数量1000拆出来就是100万件再乘以V基本就炸了。暴力拆解最怕的就是“数量大、容量大”的组合。在很多真实题目里n和V都能到10^5量级朴素拆法根本没法跑。这时候就需要对“数量”这个维度做优化。3.2 二进制拆分把数量复杂度从O(c)降到O(log c)二进制拆分是多重背包最常用的优化手段核心思想是不需要把c[i]件物品拆成c[i]个独立物品而是拆成若干个“打包组”让这些组能组合出1到c[i]之间的任意件数。怎么拆按2的幂次来。假设某种物品有13件拆成1件、2件、4件剩下的6件单独一组。也就是1、2、4、6。为什么是6而不是8因为1247如果下一组取8那么124815已经超过13了所以剩余部分取13-76。用1、2、4、6这四组能不能组合出1到13的所有数量当然可以。要1件就用第1组3件用第1组加第2组7件用12411件用14613件用1246。这四组一共可以拼出0到13的所有整数。每组打包后的重量是w[i]乘该组件数价值是v[i]乘该组件数。把这些打包组当作0/1背包的物品就等价于原多重背包问题。复杂度从原来的O(n × c × V)降到了O(n × log(c) × V)。比如数量是1000log2(1000)约等于10相当于把1000件压成10组效率提升是肉眼可见的。提示如果某个物品的数量特别大比如接近1万二进制拆分仍然有优势。这是在工程实现中性价比最高的优化点也是多重背包问题相关文章和讨论中出镜率最高的技巧。3.3 单调队列优化当数据范围进一步收紧除了二进制拆分多重背包还有一个更强的优化单调队列优化能把复杂度压到O(n × V)。这个思路相对进阶核心是把多重背包的状态转移看作在模w[i]的剩余类上进行滑动窗口最大值查询。具体点说对于容量j考虑选k件当前物品0≤k≤c[i]转移为dp[j] max(dp[j - k × w[i]] k × v[i])这个式子可以按j对w[i]的余数分类每一类内部随着k的变化dp值在滑动窗口上取最大值。用单调队列维护这个窗口就能在O(V)时间内完成一种物品的处理。不过说句实话多数题目用二进制拆分已经够了。单调队列优化的代码复杂度高、容易写错我自己的经验是先评估数据范围只有当V和c都特别大、二进制拆分仍会超时时才值得上单调队列。新手阶段可以先把二进制拆分吃透把单调队列作为一个“听说过、知道思路”的进阶项来储备。3.4 三种背包的对比与选型思路把三种背包放在一起看它们的关系其实非常清晰类型物品数量约束二维转移方程中的状态来源一维内层循环方向单件物品复杂度0/1背包每件最多1次dp[i-1][j] 与 dp[i-1][j-w[i]]v[i]逆序O(V)完全背包每件无限次dp[i-1][j] 与 dp[i][j-w[i]]v[i]正序O(V)多重背包朴素拆解每件最多c[i]次拆成c[i]个0/1物品逆序O(cV)多重背包二进制拆分每件最多c[i]次拆成log(c[i])个0/1物品逆序O(V log c)实战中拿到一道背包题我一般会先问三个问题物品有几类每类能选几次容量有多大搞清楚这三件事选哪个模型基本就出来了。如果题目只字未提“次数”默认是无限次那就是完全背包如果说“每件物品只能使用一次”是0/1背包如果给了明确的库存数量那就是多重背包。4. 实操过程与核心实现滚动数组与完整代码4.1 从二维数组到滚动数组的内存压缩二维dp虽然好理解但空间开销很大。n1000V10000dp数组就有1000×10000个int约1000万个占内存40MB左右如果n和V都到10^5二维直接爆内存。滚动数组的思路是观察转移方程dp[i]这一层只依赖dp[i-1]这一层再往前的结果根本用不到。所以只用一维数组dp[j]在遍历物品时反复覆盖更新即可。“覆盖”这个动作有个讲究对于0/1背包内层循环必须逆序否则就会覆盖掉前一层还在使用的数据对于完全背包内层循环正序让新数据参与后续计算反而正是我们想要的。这就是前面讲循环顺序时的核心原因。4.2 0/1背包完整代码与逐行解释下面是0/1背包的Python完整实现n, V map(int, input().split()) w [0] * (n 1) # 重量 v [0] * (n 1) # 价值 for i in range(1, n 1): w[i], v[i] map(int, input().split()) 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]) print(dp[V])逐行看w和v的下标从1开始是为了让“前i件物品”的表述更直观dp[j]表示容量为j的背包能装的最大价值。外层循环每处理完一种物品dp数组就代表“考虑了前i件物品”之后的结果。内层循环从V向w[i]递减保证在计算dp[j]时dp[j-w[i]]还没被本轮更新覆盖仍然保存的是前i-1件物品的最优值。如果换成C写法也几乎一样#include bits/stdc.h using namespace std; const int MAXN 1005; int w[MAXN], v[MAXN], dp[MAXN]; int main() { int n, V; cin n V; for (int i 1; i n; i) { cin w[i] v[i]; } for (int i 1; i n; i) { for (int j V; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } cout dp[V] endl; return 0; }4.3 完全背包和多重背包的代码变化完全背包只需要把0/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])就这一个方向变化含义完全不同。正序枚举时dp[j-w[i]]在本次循环中已经被更新过可能包含当前物品多次选择的最优解所以物品可以无限使用。多重背包用二进制拆分实现时先把每种物品按组拆分再统一跑0/1背包n, V map(int, input().split()) items [] # 存拆分后的物品 (重量, 价值) for _ in range(n): wi, vi, ci map(int, input().split()) k 1 while k ci: items.append((wi * k, vi * k)) ci - k k 1 if ci 0: items.append((wi * ci, vi * ci)) dp [0] * (V 1) for wi, vi in items: for j in range(V, wi - 1, -1): dp[j] max(dp[j], dp[j - wi] vi) print(dp[V])这段代码核心在while循环里每次取2的幂次k如果k还小于等于剩余数量ci就把k件打包成一组同时ci减去kk翻倍。循环结束后如果ci还有剩余就单独打包成一组。这个剩余部分可能不是2的幂次但它能保证所有1到原始c的数量都能被组合出来。4.4 验证思路小样例手工推导样例一背包容量10三件物品物品1重量2价值3物品2重量3价值4物品3重量4价值5手动跑一遍0/1背包初始dp全为0。 处理物品1j从10到2dp[2]3dp[3]3dp[4]3dp[5]3以此类推dp[10]3。 处理物品2j5时dp[5]max(dp[5]3, dp[2]47)7。j6时dp[6]max(dp[6]3, dp[3]47)7。j10时dp[10]max(dp[10]3, dp[7]47)7。 处理物品3j6时dp[6]max(dp[6]7, dp[2]58)8。j9时dp[9]max(dp[9]7, dp[5]512)12。j10时dp[10]max(dp[10]7, dp[6]512)12。所以最优值是12方案是物品2加上物品334重量7价值459不对这里算错了。重新算dp[10]时考虑物品3dp[6]在物品2之后是7代表用物品12和物品23组合重量5价值7加上物品3的重量4总共重量9价值12符合不超过10的条件。如果物品2加物品3重量7价值9小于12所以最优方案是物品1物品2物品3重量9价值12。这个小例子可以很好地验证滚动数组的正确性。建议读者初学阶段都这么做先找一组小数据手工填表推导一遍再用代码跑两边结果对照。dp题最怕“代码能跑但不知道在算什么”手工推导能逼你真正理解每一步。5. 常见问题与排查技巧实录5.1 循环顺序写反了程序不会报错但答案是错的这个坑我踩过太多次。0/1背包内层写成正序程序语法完全没问题跑起来也不报错但答案会变成“同一件物品被反复选了很多次”也就是实际变成了完全背包。如果测试数据恰好只有一件物品可以重复选多次甚至可能碰巧得到看似合理的结果迷惑性更强。排查方法用一组很小的数据比如两件物品容量足够大把每种物品能选多次和只能选一次的结果分别算出来对比。如果代码输出明显偏大基本就是循环方向的问题。5.2 数组越界与边界条件常见的越界点有两个。一是j的下标范围内层循环写for j in range(V, -1, -1)但j w[i]时dp[j-w[i]]会访问负数下标Python会直接报错C则会出现未定义行为。所以循环下限通常是w[i]-1而不是-1。二是“恰好装满”负无穷初始化后加法溢出如果dp[j-w[i]]是-10^9再加v[i]可能变成-999999990虽然不会爆int但在某些特别严格的题目里如果你初始化用的是INT_MIN再加一个正数可能直接溢出成负数导致判断逻辑出错。稳妥做法是初始化用一个足够小但加法不会溢出的值比如-0x3f3f3f3f。5.3 复杂度预估和读题细节拿到背包题先估算复杂度不要盲目套模板。我的一般标准是n × V在10^7以内直接0/1背包在10^8左右要考虑剪枝或优化超过10^8必须用更高级的优化方案。多重背包题如果c[i]很大优先二进制拆分如果V也很大且c[i]极大单调队列优化才需要考虑。还容易忽略的是读题中的小字。题目里藏着“每种物品最多选一次”“可以重复选择”“每种物品最多选c[i]个”这些词直接决定用哪个模型。我见过不少同学因为只看了样例默认是完全背包结果交上去全错。5.4 问题速查表问题现象可能原因排查与解决答案偏大0/1背包内层循环写成正序内层循环改为从V到w[i]递减答案偏小或为0恰好装满问题但初始化错误dp[0]0其他dp[j]-INFPython一直报负数下标错误j循环范围过大循环下限改为w[i]-1多重背包朴素拆解超时复杂度O(n×c×V)太高用二进制拆分或单调队列优化二进制拆分后答案不对拆分剩余部分处理错误剩余部分单独打包不要遗漏大数组内存超限使用了二维dp改一维滚动数组最后再分享一个我自己调试背包问题时的心得不要急着在OJ上反复提交试错先用小数据把dp数组一行行打印出来看每个状态是怎么从上一步转移来的。只要你能用笔在纸上把那几步转移写明白循环方向、初始化、边界条件这些坑基本都能避开。背包问题的变种很多分组背包、二维费用背包、依赖背包本质都是在“状态定义”和“转移来源”上做文章把0/1背包这一条主线吃透后面遇到新的变种时你会有一种“哦原来只是改了个约束”的通透感。