动态规划背包问题全解析：0-1背包、完全背包与多重背包

1. 开始之前背包问题到底在求什么1.1 一个很多人没意识到的建模动作背包问题最让我惊讶的地方是它几乎覆盖了所有资源有限、选择无限的现实场景。比如你有一个容量10的背包面前有5个物品每个物品有自己的重量和价值目标是在不超过背包容量的前提下挑出总价值最大的组合。这听起来像是一个朴素的组合优化问题可一旦物品数量上到几十上百枚举所有组合就彻底不现实了2的100次方这个数字任何计算机都扛不住。所以动态规划背包问题的第一步不是写代码而是把一个实际需求翻译成一个标准的数学模型。你手里有什么资源——背包容量你有哪些决策——每个物品选还是不选你追求什么——总价值最大。这三句话写清楚了后面的代码才会有方向。我见过很多人一上来就套模板结果题目一变就懵问题就出在建模这一步跳过得太快。在C里做背包通常会把物品重量存到数组w[]价值存到数组v[]然后用dp[i][j]表示在前i个物品中做选择且总重量不超过j时能获得的最大价值。这个定义不是凭空来的它包含了两个维度一是处理到哪件物品了二是当前还剩多少容量。后面的所有优化、所有变体都是从这两个维度展开的。1.2 为什么说状态定义是这道题的分水岭很多新手对dp的恐惧其实是对状态定义的不适应。简单说状态就是我已经决定了前i个物品怎么选当前我的背包占用为j此时我的收益是多少。这个定义在数学上叫子结构它要求我们从一个小规模问题出发通过递推得到大规模问题的答案。你可能会问为什么不是当前重量恰好等于j这里面有一个很关键的约定不超过j通常更好用因为我们可以从dp[i][j] dp[i-1][j]继承一个不选当前物品的状态。如果定义成恰好等于j那么这个继承动作就非常别扭因为前i-1个物品凑出来的重量不一定是j。这也是为什么后面讨论恰好装满时需要单独处理初始化的原因。状态定义决定了转移方程。对于0-1背包每件物品有两种决策不选那么dp[i][j]继承dp[i-1][j]选那么需要先把容量j减去当前物品重量w[i]再加上价值v[i]即dp[i-1][j-w[i]] v[i]。两者取最大就得到了当前状态。这个过程就是状态的推演它的每一步都只依赖前i-1个物品的结果不依赖后面的物品——这就是动态规划里常说的无后效性。1.3 贪心失效的直观演示有一种思路是单位重量价值最大优先即贪心。用图景来说就是一个容量为10的背包三件物品分别是(重量6价值6)、(重量5价值5)、(重量5价值5)。如果按单位价值一样来挑先拿第一件剩余容量4什么都装不下总价值6。可正确答案是拿后两件总价值10。这种反例足以说明局部最优拼不出全局最优。动态规划为什么能解决这个问题因为它不是一次性决定选哪些而是把整个决策过程拆成一步步的子问题并且用一张二维表把这些子问题的答案全部存下来。每个状态都保存了在这个决策阶段、这个容量限制下的最优收益最终dp[n][C]n个物品都决策完容量限制为C就是全局最优。这一节的核心结论是遇到组合优化的题目先尝试用决策阶段资源限制两个维度描述状态如果状态能从小范围递推到全范围那么动态规划大概率就是那把钥匙。背包问题是这类思想的入门钥匙而C的高效数组和显式循环刚好适合把整个过程清晰落地。2. 0-1背包从二维dp表到滚动数组代码是怎么一步步变短的2.1 最朴素的二维写法先能跑通我建议所有人在理解阶段先写最朴素的二维版本不要直接背一维优化版。原因很简单二维版本的行列含义和状态转移一一对应出错时还能把dp表打出来逐行排查。下面这段代码就是0-1背包的基准版。#include iostream #include vector #include algorithm using namespace std; int main() { int n, C; cin n C; vectorint w(n 1), v(n 1); for (int i 1; i n; i) cin w[i] v[i]; // dp[i][j]: 前i个物品中选总重量不超过j的最大价值 vectorvectorint dp(n 1, vectorint(C 1, 0)); for (int i 1; i n; i) { for (int j 0; j C; j) { // 不选第i个物品 dp[i][j] dp[i - 1][j]; // 选第i个物品前提是容量足够 if (j w[i]) { dp[i][j] max(dp[i][j], dp[i - 1][j - w[i]] v[i]); } } } cout dp[n][C] endl; return 0; }注意这里的循环j是从0到C每次都先继承不选的结果再比较选的结果。这样的写法逻辑最直观运行效率也足够应付多数题目n1000时约百万次操作。但代价是多开了一个二维数组内存复杂度是n乘C。2.2 省掉一个维度的勇气从哪来二维dp表每一行的更新只依赖上一行而且只依赖当前列j和左边的列j-w[i]。这意味着第i行写完以后第i-1行就再也用不到了。那我们可不可以只用一个一维数组让它在原地更新答案是可以但更新方向有讲究。一维状态dp[j]的含义变成当前已经处理完前i件物品时容量不超过j的最大价值。内层循环从C向j递减到w[i]这样在计算dp[j]时dp[j-w[i]]还没有被本轮更新覆盖它仍然是上一轮处理i-1件物品的结果这正是我们想要的。从二维压到一维本质上是用更新时机代替行号。如果你从前往后更新dp[j-w[i]]已经被本轮更新过代表的是考虑了当前物品后的状态那么当前物品就可能被反复选入背包0-1背包就悄悄变成了完全背包。这也是很多人在接触完全背包时突然理解循环顺序的原因。2.3 为什么逆序遍历这么反直觉却必须这么做逆序遍历让很多人困惑同样是更新一个数组为什么反过来就对了我们用一个小例子说明。假设只有一个物品重量2价值3容量C3一维数组初始全0。正序遍历j从0到3。当j2时dp[2]会更新为dp[0]33当j3时dp[3]会更新为dp[1]33。到这里看似没错。但如果在同一个物品下继续看j循环只有一轮看起来正序也没问题问题出在第2个物品到来时正序会让第2个物品更新用到的dp[j-w[j]]可能已经被第2个物品改动过。更直接的例子是两个相同物品重量2、价值3容量4。正序在j4时dp[4] dp[2]3而dp[2]在同一轮已经变成3所以dp[4]变成了6相当于选了两次同一种物品。逆序则保证dp[2]在dp[4]更新时仍旧是上一轮的值0所以dp[4]3只有一个物品被选中。一句话总结逆序是为了让每个物品最多被选一次。代码中从C到w[i]递减循环天然实现了这个效果。理解这一点后你会觉得背模板一点也不虚。2.4 你最终会留在编辑器里的0-1背包模板一维优化的最终代码大概长这样#include iostream #include vector #include algorithm using namespace std; int main() { int n, C; cin n C; vectorint w(n 1), v(n 1); for (int i 1; i n; i) cin w[i] v[i]; vectorint dp(C 1, 0); for (int i 1; i n; i) { for (int j C; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } cout dp[C] endl; return 0; }这段代码就是0-1背包的标准形态。记住两个要点一重循环遍历物品二重循环逆序遍历容量转移只写一行max。很多变种都在这两个要点的排列组合上做文章。3. 完全背包与多重背包两个方向的变体同一个套路3.1 完全背包只是一行代码的事但原理不能只记结论完全背包和0-1背包的区别是每种物品有无限件。你可能会想到拆成很多个相同物品但那会让物品数量膨胀到无法接受。更好的做法是直接修改内层循环顺序——从正序遍历容量。为什么正序就能实现无限取回到2.3的例子里正序遍历时dp[j-w[i]]已经包含了当前物品的信息所以再更新dp[j]时相当于允许物品被重复使用。这种复用正好对应无限件。代码只需要把内层循环改成for(int j w[i]; j C; j)。但这里有一个容易忽略的边界dp[j]继承的不选状态。由于是正序同一轮里dp[j-w[i]]可能已经更新过因此完全没有必要再显式写不选分支。实际上dp[j] max(dp[j], dp[j-w[i]]v[i])这一句在正序循环下自动完成了多次加法也就是允许多次放入。我建议你亲手用一个小数据跑一遍二维表把内层每个dp[j]的变化写出来很快就能理解这个反直觉的循环顺序。3.2 多重背包的二进制拆分到底拆的是什么多重背包给每种物品一个数量上限k比如某种物品最多有10件。最朴素的思路是把10件拆成10个独立物品做0-1背包。但k很大时比如1e5拆分成单个物品会让总件数爆炸。二进制拆分是一个聪明得多的办法把k拆成若干个数这些数能组合成0到k之间的任意整数但个数只有O(log k)个。拆分规则是每次取2的幂次比如k10拆成1、2、4、3因为下一个8会让总和超过10所以最后取10-1-2-43。用这些打包后的物品做0-1背包复杂度从O(nkC)降到O(nlog kC)。不少人第一次看到这里会疑惑1、2、4、3真的能覆盖0到10吗我们验证0什么都不用123124514624712481349234101234。所有整数都能被组合出来这就是二进制拆分的数学底子。vectorpairint,int goods; // weight, value while (k 0) { int cnt 1; // 当前批次数量 while (cnt * 2 - 1 k) cnt 1; // 这里更常用写法是逐步取1,2,4... }我给出一个稳定写法int num k; int batch 1; while (num 0) { int take min(batch, num); int nw take * w; int nv take * v; // 将这个nw/nv作为0-1背包的一个物品 num - take; batch 1; }拆分完成后再用标准0-1背包的逆序循环处理这些打包物品即可。3.3 分组背包把每组只能选一个翻译成状态转移再进一步物品被分成若干组每组最多挑一件。这看起来和前面的都不一样但状态转移还是一句话枚举每一组对组内的每个物品都尝试一次选它。具体做法是在一维dp基础上外层循环遍历组内层先循环容量逆序保证每组的物品最多选一个再循环本组内的物品。注意顺序一定是先容量后物品否则同一组的多个物品会相互影响导致一组里选了好几件。vectorint dp(C 1, 0); for each group g: for (int j C; j 0; j--) { for each item in group g: if (j item.w) { dp[j] max(dp[j], dp[j - item.w] item.v); } }为什么这样就能保证每组最多选一个因为容量循环是逆序的dp[j]更新时用到的dp[j-w]还是上一组的结果也就是说当前组内的物品互相之间不会叠加。如果你把物品循环放在外层容量放在内层同一组内的不同物品会在一次容量遍历里互相更新可能会导致一组选多件。3.4 一张表看清三个背包的差异背包类型每种物品数量容量循环方向核心思想典型复杂度0-1背包最多1件逆序从C到w[i]每件选或不选O(n*C)完全背包无限件正序从w[i]到C利用本轮更新实现重复选O(n*C)多重背包有限件k逆序对拆分后的物品二进制拆分压物品数O(nClog k)分组背包每组最多1件逆序先容量后组内物品组内互斥O(组数C组内大小)实际做题时先判断物品的使用限制再决定用哪种循环方向比硬记模板的适用场景可靠得多。判断依据很简单物品能不能重复用能就正序不能就逆序有限个但又不能简单当成完全背包先二进制拆分再按0-1背包处理。4. 真正决定你过不过的细节初始化、边界与带约束的变体4.1 恰好装满和不超过容量dp[0]之外的区别默认背包问题求的是不超过容量C的最大价值初始化全部为0是合理的因为什么都不装就是合法的空包方案价值0。但如果题目改为恰好装满容量C的最大价值情况就不同了。未达到恰好装满的状态是非法的不能简单用0表示否则会把非法方案混进来。标准做法是vectorint dp(C 1, -1e9); // 或 INT_MIN / 2 dp[0] 0;因为只有重量为0的状态是合法的起点其他容量的恰好值当前都不存在用负无穷标记为不可达。在转移时如果dp[j - w[i]]是负无穷那么dp[j]也不会被误更新成合法值因为负无穷加任何价值还是负无穷C里不要直接用INT_MIN加正数可能导致溢出通常用-1e9或INT_MIN/2更稳。初始化之差能直接把一题变成另一题。很多模板默认把所有dp初始化为0遇到恰好装满题直接样例通过、大量数据挂掉就是这个原因。4.2 遇到未定义状态时用负无穷还是-1用-1表示不可达可以吗可以但你的转移就要多写一个判断if (dp[j - w[i]] ! -1) { dp[j] max(dp[j], dp[j - w[i]] v[i]); }用负无穷则不需要这种判断因为负无穷价值还是负无穷取max时不会影响其他合法状态。代价是要时刻小心溢出。我的习惯是初始化-1e9因为题目价值总和通常不会超过1e9负无穷足够无穷。还有一种情况是求方案数dp[i]表示凑成重量i的方案数初始化dp[0]1转移时dp[j] dp[j - w[i]]内层循环方向根据背包类型变化。此时就不需要负无穷了因为方案的0和1都是合法语义只需要保证dp[0]1其余为0即可。由此可见同一个dp数组因为目标不同初始化和转移是完全不同的写法。4.3 二维费用背包状态再多一维逻辑不变当每个物品不仅消耗重量还消耗体积或某种容量背包就有两个限制条件。解决思路很简单状态再加一维从dp[j]变成dp[j][k]分别表示重量不超过j且体积不超过k时的最大价值。vectorvectorint dp(C 1, vectorint(V 1, 0)); for (int i 1; i n; i) { for (int j C; j w[i]; j--) { for (int k V; k t[i]; k--) { dp[j][k] max(dp[j][k], dp[j - w[i]][k - t[i]] v[i]); } } }注意内外两维容量都要逆序原因是同一个物品不能被同时选两次。很多时候二维费用的题目对数组大小的限制更严格写代码前先估算NCV会不会超内存。如果明文告诉你C和V都到1000物品n到100那要思考一下状态能不能压缩或者能不能优化成一维加另一维的递推关系。二维费用本质上还是背包只是资源维度扩展了。遇到三个限制条件时就三维dp但时间和内存往往会吃紧这时要优先考虑是否可以拆条件、减少一维或者用其他算法解决。4.4 我排查边界bug的顺序与打印dp表的技巧背包题报错时先别急着重写。我的排查顺序是检查物品数组下标从1开始还是从0开始。很多模板从1开始读入循环也要从1到n。检查容量循环边界。0-1背包用for (int j C; j w[i]; j--)完全背包用for (int j w[i]; j C; j)方向反了结果全错。检查dp初始化和输出状态。输出的是dp[n][C]还是dp[C]一维版本初始化全0还是-1e9手动造一个小数据比如n3C5把关键状态的dp变化写出来对比。打印dp表是最直接的调试手段。在一维版本中每处理完一个物品后打印一次dp数组观察每个物品是怎么滚进数组的。如果你看到某一轮容量j变化时dp[j]的数值从上一轮的值跳成了本轮被多次更新那就说明循环方向写错了。5. 把背包题练成肌肉记忆选题顺序与个人模板5.1 从零到一我建议的练习顺序不要直接刷困难题那样挫败感太强。我建议按下面这个顺序练第一步先跑通0-1背包的朴素二维代码输出答案再改成滚动数组对比结果。 第二步做几个裸题——题目明说是背包直接套模板。 第三步做需要识别出这是背包问题的题比如把一个数组分成两个和相等的子集本质是能不能凑出总和的一半。 第四步做完全背包和多重背包的裸题理解循环方向差异。 第五步做方案数、恰好装满、二维费用等变体反复练习初始化与转移。一个常见的学习误区是上来就背一维模板结果只记住了代码遇到恰好装满就歇菜。反过来如果你自己推过二维转移、亲手写过一维滚动那么任何变体你都可以从状态定义出发重新推导而不是套模板。5.2 一套可复用的C模板与改参点下面是我平时写背包题前心里默念的通用结构可以应对绝大多数背包变化#include iostream #include vector #include algorithm using namespace std; const int INF_NEG -1e9; int main() { int n, C; cin n C; vectorint w(n), v(n); for (int i 0; i n; i) { cin w[i] v[i]; } // 按需选择初始化 vectorint dp(C 1, 0); // 不超过容量 // vectorint dp(C 1, INF_NEG); // 恰好装满 // dp[0] 0; for (int i 0; i n; i) { if (0-1背包) { for (int j C; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } else if (完全背包) { for (int j w[i]; j C; j) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } } cout dp[C] endl; return 0; }对于多重背包先做二进制拆分再走0-1背包分支。对于分组背包把内层换成先容量后组内物品。这套模板的三个改参点就是初始化方式、容量循环方向、物品组内遍历顺序。记住这三个点遇到变体时你只需要思考它属于哪种。5.3 常见的伪最优解与避免背模板翻车我见过最多的问题不是不会写代码而是模板对了但题意理解偏了。比如题目要求总重量恰好等于C你用了全0初始化结果通过率惨不忍睹。再比如每种物品可以无限取但你把它当成0-1背包来做正序和逆序一字之差答案天壤之别。另一个容易翻车的地方是用int存dp值。如果物品价值和都超过20亿int会溢出。这时要用long long并把负无穷初始化改为-1e18。同样的方案数题目经常要求对某个大质数取模如果忘记模数据一大就全错。还有一个小细节读入物品时w或v可能为0。如果重量为0且价值为正那么在不超过容量的情况下0重量的物品可以无限叠加价值dp的最大值可能超出一般直觉。分析这类题时要单独考虑重量0的物品对答案的贡献防止思维盲区。6. 背包问题带给我的不止是一类题对状态机思维的延伸6.1 从背包到完全背包本质是循环顺序的变化真正练到后期你会发现背包家族的所有题目都可以用状态定义 阶段循环 容量方向统一起来。0-1和完全背包的区别只是内层循环从逆序变正序多重背包只是先加工数据再套0-1分组背包只是把决策枚举放在容量循环内。这种统一性让我对动态规划的理解上了一个台阶很多题不是新题而是旧题换了限制条件。我印象最深的是某次做一个最长子序列变体题时我试图把每个字符当成一个物品把匹配长度当成容量发现和背包问题有着完全相似的选择或不选择模型。那一刻我才意识到背包训练的真正价值是培养我把问题拆成阶段、状态、决策三件套的思维方式。拥有这种思维后看到类似划分数组子集和的问题第一反应就是试着用dp建模。6.2 为什么求方案数/最优解时初始化要一级一级审最后分享一个我自己踩过的坑求方案数时如果物品重量有0的情况dp[0] 1会出问题。比如两件物品重量都是0那么凑成重量0的方案数应该是4种都不选、选第一个、选第二个、两个都选但如果只是形式上令dp[0]1然后正常转移就能得到这个结果吗通常不行因为0重量物品不会更新dp数组中的其他格子导致很多方案没有计数。处理方式是单独统计所有重量为0的物品设它们的数量为zeroCnt那么凑成任意重量j的初始方案数要乘以2的zeroCnt次方因为每个0重物品可选可不选然后再处理正重量物品。这个坑不亲自踩一次很难想到。经过这几轮练习我现在看背包题的感觉就像看一张熟悉的地图先定位物品数量限制再决定循环方向先看是求最优值还是求方案数再决定初始化和转移。每一步都不是靠背而是靠对状态转移本身的理解。也希望这篇文章能帮你把这张地图真正画进脑子里下次遇到背包题时不再是套模板而是我在推导这个状态该怎么转移。