我最早接触背包问题是在准备算法面试的时候当时啃完了0-1背包的经典解法觉得自己已经会了。直到某天被问到一道物品可以无限取的变体才发现自己只是背下了代码模板根本没理解状态转移里那个循环顺序到底意味着什么。这大概是很多人的共同经历——0-1背包的代码背得滚瓜烂熟但换个题目背景就转不过弯来。这篇背包问题二主要聊的是从基础0-1背包出发如何扩展到完全背包、多重背包以及一堆在实际场景中高频出现的变形考法。适合刚学完基础背包、正打算进阶的读者也适合那些刷题时总在背包变体上卡壳的人。我会把状态定义、转移方程、循环顺序背后的原理讲透再配上可以直接抄的模板代码和踩坑记录争取看完这篇背包这一类题你都能心里有底。1. 0-1背包的再复盘为什么状态转移必须倒序遍历既然叫背包问题二默认你已经有0-1背包的基础。不过在我展开完全背包和多重背包之前强烈建议先把0-1背包的底层逻辑重新捋一遍——后面所有扩展本质上都是在0-1背包的状态转移方程上做文章。0-1背包的标准描述是有n件物品每件物品重量为w[i]、价值为v[i]背包容量为m每件物品最多取一次求能装下的最大价值。经典二维DP解法是dp[i][j]表示从前i件物品中选择总重量不超过j时能获得的最大价值转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) # 前提是 j w[i]这个方程的含义很直白不取第i件物品继承前i-1件物品在容量j下的结果取第i件物品则腾出w[i]的容量加上v[i]的价值。二维状态下优化成滚动数组就变成了大家最熟悉的一维写法for i in range(n): for j in range(m, w[i]-1, -1): dp[j] max(dp[j], dp[j-w[i]] v[i])关于内层循环为什么要从大到小很多教程只说防止重复取用但这个解释的颗粒度不够。我们真正要看的是一维数组在迭代过程中dp[j]同时承担了两个角色——它既是当前正在计算的、可能已经包含了第i件物品的结果又是上一轮循环也就是只考虑前i-1件物品时保留下来的旧值。如果正序遍历计算dp[j]时dp[j-w[i]]可能已经被本轮更新过了里面装的已经是取了一次第i件物品的新值于是dp[j]就可能在一次循环里多次叠加同一件物品的价值。这正好就是完全背包需要的效果。而倒序遍历时j-w[i]一定小于j且本轮还没有被更新过所以dp[j-w[i]]一定还是上一轮的旧值自然就保证了每件物品最多取一次。提示判断一个循环顺序的含义不要死记结论直接盯着dp[j-w[i]]的来源有没有被本轮污染即可。这个思路在推导很多背包变形的时候都非常好用。我见过不少同学在二维转一维时直接套模板完全不理解倒序的意义。结果一旦题目换成恰好装满方案数二维费用这类问法就会在循环顺序上栽跟头。所以接下来的完全背包和多重背包我会一直围绕这句话展开读懂遍历顺序就读懂了背包问题一半的变体。2. 完全背包正序遍历的直觉理解与代码落地完全背包和0-1背包的唯一区别就是每件物品不再限制取用次数而是可以用无限次。这看起来只是一个小改动却让很多初学者困惑为什么内层循环正序遍历就能解决问题下面把这个问题拆开讲清楚。2.1 为什么正序能表达无限次取用我们从语义上来推。假设当前正在处理第i件物品外层循环已经执行到了第i轮。在一维数组dp中倒序遍历时dp[j-w[i]]代表的是只使用前i-1件物品、容量为j-w[i]时的最优结果因为没有第i件物品的参与所以第i件物品不可能被重复取。正序遍历则完全不同当我们从左往右更新dp[j]时小容量的dp[j-w[i]]已经被本轮更新过了。换句话说dp[j-w[i]]这个值本身就可能已经包含了取了一次第i件物品的结果。此时再用它来推导dp[j]就相当于在已有一次第i件物品的基础上又加了一次这正是可以无限取用的语义。为了把这个问题看得更直观我用一个小例子手推一遍。假设只有一件物品重量2、价值3背包容量为5初始dp数组全是0。正序遍历j 2, 3, 4, 5jdp[j-w[i]]更新后 dp[j]2dp[0] 0max(0, 03) 33dp[1] 0max(0, 03) 34dp[2] 3max(0, 33) 65dp[3] 3max(0, 33) 6可以看到容量4时dp[4]被更新为6意味着这件物品被取用了两次容量5时同理dp[5]也相当于取用了两次并剩了1单位容量。这就是完全背包和0-1背包在代码上唯一的差别。2.2 完全背包完整模板def complete_knapsack(n, m, w, v): dp [0] * (m 1) for i in range(n): for j in range(w[i], m 1): # 注意这里是正序 dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[m]代码主体和0-1背包几乎一模一样唯一的区别就是内层循环的起点和方向。在实际做题时我自己习惯把这两种情况的循环写成两种模板避免现场推倒重来问题类型内层循环写法语义0-1背包for j in range(m, w[i]-1, -1)每件物品最多取一次完全背包for j in range(w[i], m1)每件物品可以取无限次2.3 完全背包的常见变体最少硬币数完全背包在面试中最常见的形式其实是给你若干面值的硬币求凑出某个金额所需的最少硬币数或者反过来问有多少种凑法。前者的典型就是零钱兑换类问题后者的典型是组合总和类问题。这类题目不会直接说背包你需要自己识别出物品、容量和优化目标。拿最少硬币数来说物品是各种面值的硬币背包容量是要凑的金额每枚硬币可以用无限次状态定义不再是最大价值而是所需的最少硬币数量。转移方程可以写成def min_coins(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for coin in coins: for j in range(coin, amount 1): dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1这里有个容易踩的坑是初始化。因为是求最小值dp数组不能初始化为0否则所有dp[j]都会被0覆盖永远得不到正确答案。正确做法是初始化为一个大数只把dp[0]设置为0表示凑出金额0不需要任何硬币。这个细节我在初学的时候吃过不少亏推荐大家在做背包变形题时先把目标是什么、初值应该是什么写在草稿纸上再动手。3. 多重背包三种解法与二进制拆分原理多重背包是指每个物品有固定数量限制第i件物品最多能取c[i]件。它介于0-1背包和完全背包之间既不是只能取一次也不是无限取。这个有限次数的设定来自很多真实场景比如库存有限的商品、限购的商品等。3.1 朴素做法拆成0-1背包最直接的想法就是把第i件物品的c[i]件副本全部列出来每一件都当作独立的0-1物品。比如3件重量为2、价值为3的相同物品拆成3件独立的物品后问题就退化成了普通的0-1背包。def multiple_knapsack_naive(n, m, w, v, c): dp [0] * (m 1) for i in range(n): for _ in range(c[i]): # 把每件物品拆成 c[i] 个独立物品 for j in range(m, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[m]这种做法逻辑最简单、最不容易出错但时间复杂度是 O(m * Σc[i])。一旦单个物品数量很大比如c[i]达到10^5直接拆分就会超时。所以实际的竞赛和面试场景里需要更快的方法。3.2 二进制拆分优化把10万次循环压成14次二进制拆分是一种非常优雅的优化它的核心思想是任何一个正整数c都可以用若干个2的幂次1, 2, 4, 8, ...以及一个余数来表示。比如c13可以拆成1、2、4、6因为1247剩余6。这样拆出来的每一组物品在0-1背包中要么整体选、要么整体不选通过组合不同组的选/不选状态就能表达出0到13之间的任意取用数量。为什么可以这样因为1、2、4、6这四个数通过选或不选能组合出0到13之间的所有整数1 - 0或12 - 可组合出0到1234 - 可组合出0到76 - 可组合出0到13这样一来原本需要13次循环处理的物品变成了4组新物品每一组还是跑一轮0-1背包逻辑。如果c[i]10^5拆出来大约只要14组效率提升非常明显。def multiple_knapsack_binary(n, m, w, v, c): dp [0] * (m 1) for i in range(n): k 1 while c[i] 0: cnt min(k, c[i]) weight cnt * w[i] value cnt * v[i] for j in range(m, weight - 1, -1): dp[j] max(dp[j], dp[j - weight] value) c[i] - cnt k 1 return dp[m]我特别提醒一点拆分时最后一组不是补到最近的2的幂而是取剩余数量。以c13为例如果拆成1、2、4、8总数是15超过了13就会选出超过实际库存的组合这在逻辑上是错的。所以必须用剩余数量作为最后一组。3.3 什么时候用单调队列优化二进制拆分已经能覆盖绝大多数场景但在c[i]非常大、且m也比较大的情况下还有一种基于单调队列的优化可以把时间复杂度压到 O(n*m)。它的推导比较复杂需要把状态转移按照余数分组来看本质是利用滑动窗口维护同一组余数下的最大值。不过说实话我在竞赛之外的实际项目里几乎没遇到过必须用单调队列才能解决的多重背包场景。如果你只是准备面试和常规笔试二进制拆分完全够用如果目标是竞赛选手可以再深入研究单调队列优化。我的建议是先把前两种写法练熟不要一上来就啃最难的优化否则容易产生挫败感。4. 背包问题的四类经典变形每一类都值得单独攻克背包问题的难点不在基础模型上而在变形。我总结了面试和竞赛里出现频率最高的四类变形每一类都有自己独特的状态设计和边界处理下面逐个拆解。4.1 恰好装满与可行方案是否存在普通的背包问题求的是不超过容量m的最大价值而有些题目会要求恰好装满容量m时的最大价值或者问能否恰好凑出某个重量。状态定义不变但初始化方式要改。如果是求最大价值且要求恰好装满dp[0]0其余初始化为负无穷如-inf这样那些不能恰好装满的状态就不会被错误地当作合法解。如果只是问是否存在某种组合则初始化为Falsedp[0]True转移逻辑用或运算dp [False] * (m 1) dp[0] True for i in range(n): for j in range(m, w[i] - 1, -1): dp[j] dp[j] or dp[j - w[i]]这里隐藏着一个非常容易错的点如果你用一维滚动数组写方案是否存在内层循环仍然必须倒序否则同一件物品会被重复使用。我曾经在一次模拟题里就因为这个疏忽把0-1背包的能否凑出写成了可以重复取的版本排查了很久才发现是循环方向的问题。4.2 方案数统计如果题目要求凑出重量m的方案总数状态定义就变成了dp[j]表示凑出重量j的方案数。初值设置依然是dp[0]1因为凑出0的方案是什么都不选这一种。转移方程则是累加而不是求maxdp[0] 1 for i in range(n): for j in range(w[i], m 1): dp[j] dp[j - w[i]]需要注意的是上面这段代码对应的是完全背包每个物品可以无限取用的方案数。如果是0-1背包的场景也就是每个物品最多取一次内层循环要倒序dp[0] 1 for i in range(n): for j in range(m, w[i] - 1, -1): dp[j] dp[j - w[i]]这两段代码的区别很多人做题时完全不区分。但如果你仔细推敲会发现它背后就是遍历顺序对使用次数限制的表达跟前面讲的完全背包、0-1背包一模一样。能在这个层面看清变体之间的统一性才算真正吃透了背包问题的模型。4.3 二维费用背包有些题目里物品不仅消耗重量还消耗另一种资源比如重量和体积同时受限制。此时状态要从一维变成二维dp[j][k]表示重量不超过j、体积不超过k时的最大价值。转移方程也很自然# 0-1背包二维费用版本 dp [[0] * (V 1) for _ in range(m 1)] for i in range(n): for j in range(m, w[i] - 1, -1): for k in range(V, t[i] - 1, -1): dp[j][k] max(dp[j][k], dp[j - w[i]][k - t[i]] v[i])二维费用背包在面试题里不算特别高频但一旦出现往往是因为它需要一个识别额外约束的思维跳跃。比如有一类题目把物品数量也当作一维费用来处理即物品数量和使用次数受限本质上也属于二维费用背包的范畴。遇到这类题建议先把两种资源的限制分别列出来再确定状态数组是二维还是三维不要一看到两个限制就直接上三维数组。4.4 分组背包给若干个组每组内最多选一件物品目标是求最大价值。这是另一种常见的变形典型场景比如每类课程里选一门来上每组优惠券里选一张等。分组的处理方式是外层先遍历组中层遍历容量内层遍历组内物品。def grouped_knapsack(groups, m): dp [0] * (m 1) for group in groups: # 先遍历组 for j in range(m, 0, -1): # 再遍历容量倒序 for item in group: # 最后遍历组内物品 if j item[w]: dp[j] max(dp[j], dp[j - item[w]] item[v]) return dp[m]这种嵌套顺序经常让人困惑为什么要先遍历组、再遍历容量因为如果先遍历物品就会破坏每组只能选一件的约束。先遍历容量并倒序可以保证同一个容量下每个组最多只有一个物品被纳入决策。换句话说组与组之间是互斥的而不是任意组合的。5. 邻接场景里那些出乎意料的坑前面讲了很多理论推导和模板但真正到了做项目或者刷题时坑往往藏在细节里。我把这几年遇到的典型问题整理成一块给大家做个集中的避坑清单。5.1 数组越界的边界处理二维DP转一维后dp[j-w[i]]只能在j w[i]时访问这几乎是所有背包模板里都要处理的问题。但很多人在写完全背包时容易犯一个错误就是把循环写成for j in range(1, m1)然后在循环体里加if j w[i]。这样做虽然逻辑上没错但每次循环都多一次判断而且代码可读性也差。更推荐的做法是把循环起点直接设为w[i]从编码上杜绝越界for j in range(w[i], m 1): # 完全背包 dp[j] max(dp[j], dp[j - w[i]] v[i])同理0-1背包的倒序写法也建议写成for j in range(m, w[i]-1, -1)而不是从m写到1再判断。5.2 初始化最小值问题和最大值问题要用相反的初值求最大值时dp初始化为0因为不装任何东西时价值至少是0求最小值时dp初始化为无穷大因为没有任何已知方案时凑出目标的代价应该是无法完成。这个道理说起来简单但很多人在做零钱兑换类题目时会把dp初始化为一个很大的数却忘了给dp[0]0导致所有状态都不可达。一个更隐蔽的场景是恰好装满求最小代价。此时不仅dp[0]0其他状态都要初始化为无穷大。这与不超过容量的初始化是完全不同的我建议在每道背包题开始敲代码前先用一句话确认清楚题目问的是不超过还是恰好等于——这比任何优化都重要。5.3 一维滚动数组的空间复用误区用好滚动数组的前提是你得清楚地知道某一轮循环中dp[j]到底代表的是旧值还是新值。我在调试多重背包问题时见过一种常见错误用一维数组实现多重背包的朴素拆分但内层循环写成了正序导致同一件物品被无限使用输出结果会偏大。这个错误的根源就是没有理解倒序防止重复使用的核心语义。为了彻底避免这类问题我的方法是在任何需要0-1背包语义的地方都写成倒序任何需要完全背包语义的地方都写成正序不确定时先用小规模数据手工推一遍dp变化再决定循环方向。5.4 数据规模与时间复杂度的事前评估写多重背包前先估算总拆分量级。如果 Σc[i] 和m的乘积在10^7以内朴素拆分可以接受如果超过10^8基本就会超时必须上二进制拆分或单调队列优化。这属于动手前就该想清楚的问题而不是写完代码后才发现跑不动。我自己的习惯是拿到题先看数据范围快速判断采用哪种写法绕开超时的坑。下面给一个小表供参考数据规模特征推荐做法时间复杂度n≤100, m≤1000c[i]小朴素拆分O(m·Σc[i])n≤100, m≤1000c[i]大二进制拆分O(m·Σlog(c[i]))n≤1000, m≤1000c[i]极大单调队列优化O(n·m)5.5 完全背包的物品顺序在计数问题中会改变答案这是一个很多人都会忽略的点同样是凑出某种金额的方案数如果题目说的是组合数不考虑顺序和排列数考虑顺序代码会完全不同。组合数场景下外层遍历硬币面值、内层遍历金额统计的是不考虑选择顺序的方案排列数场景下外层遍历金额、内层遍历硬币面值统计的则是不同选择顺序也算不同方案的排列。很多初学者搞不清这个区别导致同样一套代码换一道表述不同的题就不能通过。我的经验是见到方案数先确认是否考虑顺序再决定循环内外层的嵌套方式。这一步想清楚了代码基本不会跑偏。6. 从模板到实战我自己的解题心法与扩展思路前面五段把背包问题的主要类型和关键细节都过了一遍但我还想从更宏观的视角分享一些实战层面的经验。因为等你真正刷题或者面试时会发现题目从来不会直接告诉你这是一个背包问题你需要自己做模型识别和转化。6.1 三步识别法我在拿到一道疑似背包的题时通常按三步走。第一步找容量题目里有没有一个总量限制比如金额上限、空间上限、时间上限。第二步找物品是否存在若干可选的东西每样有消耗和收益。第三步找约束每样东西能用几次。是只能一次、无限次还是有固定次数这三个问题想清楚后基本就能确定用0-1背包、完全背包还是多重背包。比如有一道经典面试题问给你一个整数数组coins和一个总金额amount求凑出该金额的硬币组合数。这里容量就是amount物品就是coins每个硬币没有数量限制所以是完全背包。再比如每个商品只能买一次在预算内求最大满意度这就是标准的0-1背包。识别过程不需要很高深的技巧关键在于养成分类的思维习惯。6.2 空间优化什么时候可以用一维数组当我最初学习背包问题时也曾疑惑为什么不直接写二维数组非得搞个一维滚动数组。后来在实际编码中才真正体会到一维数组的好处不只是省空间——写起来更简洁而且出bug后更容易定位。但一维数组并非万能。需要记录具体选了哪些物品的问题或者需要回溯方案的题目往往要用二维数组保留完整的转移信息。我做过一道输出选择方案的题目单纯用一维数组只能得到最优价值无法反推选了哪些物品。如果遇到这类需求建议直接用二维DP并额外记录决策路径不要为了空间牺牲可追溯性。6.3 前几轮刷题的正确姿势如果你是初学者我建议不要直接进入多重背包的单调队列优化也不要一开始就做一堆组合变形题。先把0-1背包的二维写法写熟再转一维写法再扩展完全背包最后才是多重背包。每一步都要求自己能讲清楚循环顺序为什么这么写。这个能讲清楚的标准比任何题量都重要。我推崇的学习路径是先手推一遍小规模状态转移表再对照代码验证然后做几道同类型题强化对模型的理解最后尝试总结不同变体之间的异同形成自己的解题模板。这个过程并不需要特别高的智商只要足够细致每个人都能掌握。6.4 扩展延伸背包问题在其他领域的影子很多人以为背包问题只在刷题和竞赛里出现但实际上它的模型在资源分配、任务调度、投资组合、存储规划等场景中都能找到影子。比如项目管理中在有限预算下选择高收益任务本质上就是0-1背包仓库库存有限但品种多样每种货物有固定库存本质上就是多重背包云计算资源分配里不同规格的虚拟机组合满足计算需求也可能转化为背包模型。这也是为什么有时候我会建议读者在学完背包基础后抽空想一下这个模型还能用在哪。一旦你有了这种迁移意识遇到现实中的资源分配问题时思维就会比别人多一层抓手。6.5 最后的建议刷题之外动手实现一个小工具如果只是对付笔试题上面的内容已经足够。但如果想真正加深对背包问题的理解我建议你动手写一个通用的背包求解器小工具输入物品的重量、价值、数量限制自动选择0-1、完全还是多重背包的逻辑来求解并输出最大价值和具体选择方案。这个工具我当年自己实现过一遍过程中把二维DP、一维滚动数组、最优方案回溯全都实践了一遍对背包问题的理解深度完全是读十篇教程都比不了的。写完之后你会发现自己再看任何背包变形题都能一眼看穿它本质上是哪类模型、状态怎么定义、初始化该设什么。这种看穿的感觉就是写这类博文我最想传递给你的东西。