0/1背包和完全背包问题前段时间给团队做算法内部分享聊到动态规划我上来先问了大家一个问题假设你是一个背包客面前有5件物品每件只能拿一次你怎么在不超过负重的前提下让总价值最大接着我又追问如果改成每件物品可以无限拿比如水和干粮策略会有什么变化在场的几个同事犹豫了一下答案各不相同。这其实就是0/1背包和完全背包的核心区别。只能拿一次和可以拿无数次两个字的差别背后的状态转移逻辑完全不同。很多人算法题刷了不少一遇到背包就背模板一个倒序遍历一个正序遍历但问为什么答不上来。这篇文章我就把自己从原理到代码再到踩坑的完整理解写下来希望能帮到正在准备算法面试、或者工作中需要做资源分配方案的开发者。1. 两种背包模型的本质差异一个选一次一个选到饱1.1 0/1背包到底在描述什么场景0/1背包的0/1指的就是每件物品只有两种状态拿1或不拿0不存在拿半个或者拿两个的情况。这是最基础的背包模型也是后面所有背包问题的地基。举个最直观的例子你要去露营帐篷、睡袋、炉具、食材、水每样东西都有重量和价值背包容量有限。帐篷重3公斤价值800睡袋重2公斤价值600食材重2公斤价值500……你不可能带两个帐篷每件物品决策一次选或者不选让总重量不超过负重总价值最大。这就是0/1背包的经典决策过程。这类问题在真实工程里也有大量影子。比如服务器资源调度一批任务每个任务占一定内存、产生一定收益服务器总内存有限每个任务最多执行一次怎么选择任务集合让总收益最大再比如广告投放预算分配每个渠道有固定成本、预估转化价值预算有限每个渠道要么投要么不投。这些都是0/1背包的形态。1.2 完全背包的无限量约束改了什么完全背包和0/1背包的唯一区别是每件物品可以取无限次。同样负重限制下水、压缩饼干、急救包这种东西你想带多少带多少只要总重量扛得住。别小看这个变化它直接改变了子问题的结构。0/1背包里处理完第i件物品后这件物品不会再次出现但完全背包里处理完第i件物品后你还可以继续选择它因为它的数量是无限的。通俗点说0/1背包是每个商品限购一件完全背包是自助餐随便拿只要盘子装得下。这个区别体现在状态转移方程上就差一个下标。但差一个下标意味着两套完全不同的循环策略。很多人就是在这里开始混淆的后面我会把方程拆开讲透。2. 状态转移方程推导从二维DP看清两种选择的本质2.1 状态定义和初值设置不管哪种背包第一步都是定义状态。假设有n件物品背包容量为W第i件物品的重量是w[i]价值是v[i]。定义dp[i][j]为考虑前i件物品在容量为j的背包中能获得的最大价值。这个定义对0/1背包和完全背包都通用。有了状态定义接下来就是初值。当i0时一件物品都不考虑不管容量多大能获得的价值都是0。当j0时容量为0什么也装不下价值也是0。所以dp[0][j] 0对任意j成立dp[i][0] 0对任意i成立。建议第一次学背包的人别急着跳去一维写法先老老实实把二维DP表格手推一遍。我用一个具体例子容量W 10三件物品分别是重量3价值4、重量4价值5、重量5价值6。手推一遍0/1背包的完整表格你会发现每个格子都对应一个选/不选的决策过程这种手感对后面理解一维优化至关重要。2.2 0/1背包的决策逻辑只能从前一轮继承0/1背包处理第i件物品时面临两个选择不选第i件物品那dp[i][j]继承前i-1件物品在容量j下的最优解即dp[i-1][j]。选第i件物品前提是j大于等于w[i]此时需要腾出w[i]的容量给第i件物品前i-1件物品只能用剩下的j-w[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])其中j w[i]。注意看方程右侧两个来源都来自i-1这一行也就是说第i件物品的决策只依赖前i-1件物品的结果不会回头再考虑自己。因为0/1背包的物品只能选一次一旦决策完第i件物品它就从候选列表里消失了。这就是为什么0/1背包的状态转移要用上一行的数据。2.3 完全背包的决策逻辑允许原地自更新完全背包第i件物品的状态转移方程是dp[i][j] max(dp[i-1][j], dp[i][j-w[i]] v[i])其中j w[i]。对比一下就能发现唯一区别在第二项0/1背包用的是dp[i-1][j-w[i]]完全背包用的是dp[i][j-w[i]]。多了一个i而不是i-1含义完全不同。dp[i][j-w[i]]表示的是已经考虑过第i件物品之后在容量j-w[i]下的最优解。也就是说选完一件第i件物品后容量还够你可以继续选第二件、第三件因为状态里记录的已经是允许重复选的结果。用一个场景帮助你记忆如果当前是0/1背包你拿了一件帐篷下一轮决策时帐篷就不再出现在选项里了如果是完全背包你拿了一瓶水下一轮还可以继续拿水因为水是无限量供应的。这个i和i-1的差异是最核心的区别也是后面遍历顺序差异的总根源。理解了它你就不需要死记谁正序谁倒序这类口诀了。3. 一维滚动数组与遍历顺序最容易翻车的关键细节3.1 从二维降到一维空间优化的原理二维DP的空间复杂度是O(nW)当W很大比如10^6级别时二维数组直接爆内存。好在每行只依赖上一行的数据可以用一个一维数组滚动更新把空间复杂度降到O(W)。一维数组dp[j]的含义是容量为j的背包在当前已处理的物品条件下能获得的最大价值。每处理一件物品就原地更新数组。但降维之后遍历顺序就成了生死攸关的问题。顺序写错答案必错这是初学者踩得最惨的坑。3.2 0/1背包必须倒序遍历容量原因只有一个先看代码。0/1背包一维写法vectorint dp(W 1, 0); for (int i 1; i n; i) { for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }内层循环为什么要从大到小假设容量循环是正序for (int j w[i]; j W; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); }当j从小往大走时dp[j - w[i]]已经被本轮循环更新过了。这个更新的值可能已经包含了选第i件物品的结果。于是当你计算dp[j]时如果不小心又用到了这个值就相当于第i件物品被选了两次——这在0/1背包里是绝对不允许的。举个例子物品重量2价值3W5正序遍历时j2dp[2] max(dp[2], dp[0]3) 3此时dp[2]已经被更新为包含这个物品。j4dp[4] max(dp[4], dp[2]3) 6但这里的dp[2]已经被本轮更新为3了于是dp[4]变成了6相当于这件物品被选了两次。倒序遍历则完全避免了这个问题。因为j从大到小dp[j-w[i]]对应的容量更小在上一轮循环中还没有被更新它保存的是前i-1件物品的旧值正好满足0/1背包每件最多选一次的约束。注意二维写法里0/1背包的容量正序倒序都可以因为dp[i][j-w[i]]和dp[i-1][j-w[i]]是不同行天然隔离。但一维写法必须倒序这是空间压缩的代价。3.3 完全背包必须正序遍历容量原因同样只有一个vectorint dp(W 1, 0); for (int i 1; i n; i) { for (int j w[i]; j W; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }完全背包内层循环必须从w[i]正序遍历到W。原因正好相反我们希望dp[j - w[i]]是已经被本轮更新过的值这样它才包含继续选取第i件物品的可能。正序遍历时容量小的j先被更新容量大的j在计算时可以直接复用新的dp[j-w[i]]从而实现无限取用。还是物品重量2价值3的例子W5j2dp[2] 3选了一次。j4dp[4] max(dp[4], dp[2]3) 6但这里的dp[2]是刚才更新过的3代表可以再选一次于是两件物品的总价值6被计算出来了。j5dp[5] max(dp[5], dp[3]3) ...dp[3]假设为3结果就是6表示重量5背包能装两件多一点的物品实际能装两件重量4分。验证一下容量5物品重量2价值3理论上最多放2件总重量4总价值6。完全背包正序遍历得到的dp[5]6与预期完全一致。3.4 二维写法其实没有顺序问题但要小心空间二维写法里0/1背包和完全背包的容量遍历顺序不会影响正确性因为用的是不同的行。但实践中如果你用二维数组去写完全背包状态转移写错成i-1就又会退回成0/1背包的语义调试起来反而更容易乱。我的建议是直接学一维写法一开始就把遍历顺序的原理搞清楚。因为面试官特别喜欢追问为什么0/1背包要倒序你如果能从防止重复选取和利用旧值/新值的角度答清楚这一关就稳了。4. 从代码模板到实际调试三个高频错误复盘说完了核心原理讲几个我见到的真实错误。每次带新人刷题总有人在这几个点上翻车而且报错方式还不一样有的直接答案错误有的内存溢出有的一看就是初始化搞错了。4.1 错误一0/1背包内层循环写成了正序症状结果偏大而且物品数量少、容量大时错得特别离谱因为重复取了高价值物品。排查思路先在纸上跑一个小例子验证比如上面那个重量2价值3的例子如果正序循环j2到5会发现dp[4]6明显超过了最多选一次的合理值。这个错误在面试手写代码时非常常见写顺手了容易把j--打成j。4.2 错误二完全背包内层循环写成了倒序症状答案和0/1背包一样完全退化了。因为倒序更新导致dp[j-w[i]]永远取不到本轮的新值无限取用被禁掉了。这类问题用一个小测试就能发现物品只有一件重量2价值3容量W10完全背包正确结果是15可以拿5件如果倒序遍历结果就是3只能拿一次。差距非常明显。4.3 错误三容量遍历范围写错很多人在for循环里把j的起点写成1或者忘记了j w[i]的判断条件导致dp[j-w[i]]下标越界或者出现负下标。// 错误写法没有处理j w[i]的情况 for (int j W; j 1; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); // 当j w[i]时dp[j-w[i]]是负数索引 }正确做法循环起点就是w[i]要么用for (int j W; j w[i]; j--)要么在循环体内加if (j w[i])。别小看这个细节在C里负下标不会崩溃但会产生脏数据在Python里直接IndexError一调一个准。4.4 初始化问题是恰好装满还是不超过容量刷题时最常见的一个坑是题意到底是恰好装满还是不超过容量。求不超过容量W的最大价值dp数组全初始化为0因为容量没被用完也算合法情况。求恰好装满W的最大价值dp[0]0其余dp[j]初始化为负无穷比如-1e9因为除了容量0其他容量没有任何合法方案能恰好装满只能慢慢推导出来。这个差异在实际题目中经常出现尤其是零钱兑换类题目。比如用若干硬币凑出金额W每种硬币可以用多次求最少硬币数这是一个完全背包求最小值且恰好装满的变体初始化就是dp[0]0其余dp[j]INF。如果初始化成0答案就全乱了因为在计算min的时候0永远是最小的所有状态都会停留在0。我见过有人把这种题用不超过容量的模板写结果每一组测试都能过示例一提交全WA。血泪教训拿到题目第一件事就是确认容量语义。5. 经典变体与真实场景映射背包问题不只是刷题工具5.1 变体一方案数统计有些题不问最大价值问有多少种方案凑满容量。这类题的状态转移方程从max变成累加。0/1背包方案数dp[j] dp[j - w[i]]; // j倒序遍历完全背包方案数dp[j] dp[j - w[i]]; // j正序遍历比如LeetCode的零钱兑换II就是完全背包求方案数。这类题的初始化通常是dp[0]1表示凑出0元的方案数是1不选任何硬币其余为0。5.2 变体二二维费用背包有的场景限制条件不止一个比如重量不超过W且体积不超过V或者内存不超过X且CPU占用不超过Y。这种题目需要把状态数组扩成二维vectorvectorint dp(W1 1, vectorint(W2 1, 0)); for (int i 1; i n; i) { for (int j W1; j cost1[i]; j--) { // 0/1背包倒序 for (int k W2; k cost2[i]; k--) { // 第二维同样倒序 dp[j][k] max(dp[j][k], dp[j - cost1[i]][k - cost2[i]] v[i]); } } }这类问题在服务器资源编排里很常见比如每个容器需要同时申请CPU和内存一台物理机两种资源都有限选哪些容器实例最划算。我在给一个模拟项目做容器调度优化时就遇到过类似模型。5.3 真实场景从刷题到工程很多人觉得背包问题是纯面试题实际工作用不上。我的看法是背包问题的价值不在于题目本身而在于让你建立约束条件下做组合优化的思维框架。举几个实际见过的案例广告投放某活动预算有限多个渠道各有固定成本和预期转化每个渠道最多投一次0/1背包或可重复投放完全背包选哪几个渠道组合ROI最高。物流装箱货车载重有限多种货物各自有重量和纯利润每种货物数量有限多重背包或无限完全背包怎么搭配单趟运输利润最大。人力排班项目多个每个项目需要一定工时、带来一定收益团队总工时有限怎么选项目组合。这些问题的规模可能不是几十几百而是成千上万但动态规划的框架完全复用。理解了0/1背包和完全背包的底层逻辑你遇到这些工程问题时会本能地思考状态是什么约束是什么变量是有限次还是无限次这些想清楚了代码只是时间问题。5.4 性能优化的一个实用技巧当n很大、W也很大时朴素背包的O(nW)会超时超内存。工业上常用的一种优化是单调队列优化主要针对多重背包。对于完全背包有一个基于性价比的剪枝思路把物品按单位价值排序用性价比最高的物品作为最优解的上界估计提前终止搜索。虽然不改变最坏复杂度但实际工程里能明显提速。不过这些属于进阶优化。建议先把基础版本写对、写透再考虑上优化手段不要一开始就陷进优化细节里。6. 背包问题调试的实操方法论一个快速验证框架最后一个部分分享我调试背包问题时的标准操作流程。这套流程帮我省了大量时间尤其是面试现场或者赶项目时。6.1 写代码前先用表格手推一轮不管题目看起来多简单我都会在草稿纸上画一个二维表格容量从0到W然后填三行。填完表格再写代码写出来的逻辑会清晰得多而且你手推的结果可以直接拿来测代码。比如W6物品有重量2价值3、重量3价值4、重量4价值50/1背包的表格推一遍你自然会知道dp[6]应该是多少。代码写完跑一次答案对不上就先回头查表格看是哪一格出了问题再定位是初始化还是循环方向。6.2 构造小规模测试用例验证边界调试背包问题时我习惯用三个固定用例用例1单件物品容量恰好等于重量验证dp[W] v。用例2单件物品容量远大于重量验证0/1结果是v完全背包结果是v乘以(W/w)的整数部分。用例3多件物品中有一件重量为0验证循环是否会出现死循环。特别是重量为0的物品很多人没留意。如果物品重量为0内层循环如果写成for (int j 0; j W; j)在完全背包里会不断叠加甚至陷入死循环。这类边界条件在题目里不一定出现但测试用例一定要覆盖。6.3 先对拍再提交的实战习惯面试时不能联网跑判题机所以我一般准备一套自己写的暴力递归版本作为对拍基准。小规模数据下暴力递归和背包DP的结果必然一致如果在随机生成的20组数据里都能对上代码基本就没问题。这套习惯也适用于工作里的算法模型验证。任何优化算法上线前都先跑一个朴素版本做基准对比保证优化方向正确这是工程师最基本的谨慎。6.4 识别看起来是背包但又不是背包的题目除了真正的背包题面试中还有一些伪背包比如划分数组为两个和相等的子集本质是0/1背包求是否存在子集和为总和的一半再比如最长上升子序列也可以看成一种奇怪的背包但解法完全不同。学会识别题目的真实模型比背更多模板重要得多。我在实际指导新人时经常强调拿到题目先问自己三个问题——这个问题的容量是什么物品是什么物品是否可以重复取用这三个答案写下来模型基本就定了。说回开头那个背包客问题。如果是露营三天帐篷睡袋只能各带一件这是0/1背包如果要带饮水和干粮数量不限这是完全背包。两种模型一套动态规划框架关键在于区分有限次和无限次的语义并据此选择遍历方向。我个人在实际做题和带项目中最大的体会是背包问题的遍历顺序不是需要背的口诀而是状态转移方程的自然推论。每当你模糊的时候回到二维表格里手动算几格所有疑问都会消失。希望这篇文章能帮你把这两个基础模型彻底吃透。