洛谷背包三题精讲：从01背包到多重背包的变形与踩坑指南

作为一个在洛谷上刷题混了挺久的竞赛老鸟看到这三道题号第一反应就是“经典永流传”。P1060、P2663、P1964这三道题放在一起看特别有意思它们都属于背包问题这个大框架下的变形但又各有各的坑。很多新手在这三道题上栽跟头往往不是因为不会写状态转移方程而是因为没看透题目背后的模型变化直接从01背包的代码抄过去改了改就交然后对着WA的红色大字发呆。这篇文章我就把这三道题一次性聊透不只是给你AC代码更重要的是讲清楚每道题的切入点、状态设计为什么是那样、以及一堆我当年踩过的坑和现在帮别人debug时经常发现的问题。1. 题目核心思路拆解这三题其实是一家人不少刷题的人有个误区觉得题号不同题就完全不同。实际上P1060、P2663、P1964这三道题在背包问题的分类里是一条线上的理解了P1060后面两题就是它的马甲变了变。1.1 从P1060“开心的金明”看01背包的底层逻辑P1060应该是很多人的第一道背包题题目背景是金明拿着N元预算去买东西每件物品有价格v和重要度w要求总价格不超过N同时让价格乘以重要度的总和最大。这个模型就是最标准不过的01背包。每件物品只有一个选或者不选没有第三种状态。状态定义dp[j]表示在预算为 j 的情况下能获得的最大“价格×重要度”总和。状态转移方程是dp[j] max(dp[j], dp[j - v] v * w)。这里第一层循环遍历物品第二层循环必须倒序遍历 j从总预算 N 逆序走到 v。为什么要倒序核心在于dp[j - v]这个状态在正序时可能已经在当前物品的更新中被覆盖过了这样一来会出现“同一件物品被选多次”的情况这是完全背包的逻辑不是01背包。倒序是为了让dp[j - v]保持在上一个物品完成后的旧值从源头杜绝重复选择。注意很多教材讲这里只会说“倒序防止重复选”但没说清正序在什么场景下才会“重复选”。如果一件物品只能选一次你正序遍历当计算到后面的 j 时j - v 可能已经包含了当前物品的收益再叠加一次等于同一件物品产生了两次贡献。所以永远记住01背包外层循环物品内层逆序容量。1.2 变形题的本质P2663“越越的组队”和P1964“mc生存之卖东西”P2663题意抽象一下有n个同学每个同学有一个能力值a[i]要选若干人分成两队让两队人数和总能力尽量接近问其中一队能达到的最大总能力值。这题第一眼看上去像贪心像是“尽量把能力值往一半靠”。但实际上一旦你决定选某些人进一队剩下的人自动进入二队所以我们的目标其实是在一队总人数不超过n/2的限制下让一队总能力值尽量接近总能力值的一半。这就从01背包变成了一个带两个限制条件的01背包——一个限制是能力值的总和不超总能力一半另一个限制是人数不超n/2。所以状态要开两维dp[j][k]表示当前选了 j 个人、总能力值为 k 时是否可行或者更优化的做法是dp[j]表示选 j 个人能达到的最大能力值转换成一个一维背包内嵌人数维度的结构。P1964“mc生存之卖东西”则更刁钻一点。题目大概是说你有若干种物品每种物品有数量、价值和占的格子数背包格子有限问怎么卖收益最大。这明显不是简单的01背包或者完全背包而是多重背包——每件物品有数量限制可以拿若干个但拿的数量不能超过它本身的数量。这样看来三题的递进关系非常清晰P1060每件物品1个选/不选 → 01背包P2663每件物品1个但多一个“人数”维度 → 01背包升维P1964每件物品有多个且占用容量求最大价值 → 多重背包这三部曲刷下来背包问题的基础框架基本就够了。2. 核心细节解析状态设计、边界条件与优化技巧2.1 P1060中的状态转移与边界处理P1060的约束不大v价格上限在30000以内但是物品数量最多25个所以O(n×N)的算法完全够用。直接建立一维数组dp长度N1初始化为0然后套用上面的转移方程。细节上要注意的是每一个物品的价值不是它本身的v而是v×w因为题目要求的是乘积的最大化。预算N不是体积上限里一定用满的可能选完之后还有剩余所以dp数组初始全0即可不需要特殊处理“恰好装满”的问题。最终答案就是dp[N]因为dp[j]的含义是预算j以内的最大收益随着j增加不会减少所以dp[N]是全局最大。关于复杂度外层循环物品数n内层循环容量从N到v整体O(n×N)在P1060的数据范围下绰绰有余。2.2 P2663的两维限制状态怎么定P2663这题我来细讲一下。能力值总和记为sum目标是让一队能力值最大化但不超过sum/2。另外还有人数限制不能超过总人数的一半向下取整。朴素思路是开二维数组dp[count][value]含义是“选择count个人能否达到value的总能力值”布尔型。初始化dp[0][0] true然后对每个人进行01背包式的更新。更新时外层遍历所有人内层倒序遍历人数最大为n/2更内层倒序遍历能力值最大为sum。最后一层的答案是在count从0到n/2的所有状态里找最大的value且dp[count][value]为true。这个value就是某一队能达到的最大能力值。因为两队能力值总和是sum一队最大不超过sum/2时二队能力值就是sum减去一队能力值两队差距最小。当然这个思路时间上是O(n × n/2 × sum)如果sum很大的话会有点悬。P2663的数据范围其实不算大一维换成dp[j]表示选j个人能拿到的最大能力值优化后是O(n × n/2)实际上更好写也更快。转移是dp[j] max(dp[j], dp[j - 1] a[i])但要留意这里对每个物品同学人数维度j也需要倒序否则同一个同学会被重复选多次一队人数限制会失去意义。2.3 P1964的容量抽象与多重背包处理P1964的坑在于容量不一定是重量而是“格子”。每种物品占的格子数不同数量也不同。如果你把每种物品的数量直接乘上格子数相当于生成了很多个“01背包的物品”然后跑01背包这在物品总数少的场合可以AC但物品数量一大物品总个数会爆炸。正确做法是二进制拆分或者单调队列优化。二进制拆分是最通用的方案把某一种数量为c、占格子为s、总价值为v的物品拆成1、2、4、8……个的组合每个组合看作一个独立物品转化成01背包复杂度从O(n×c×C)降为O(n×log(c)×C)。道理很简单任意0到c之间的数量都能用二进制位组合出来所以拆出来的新物品可以覆盖原物品所有可能的选择数。P1964这题还有个特别容易忽略的点背包容量是格子数而物品的“重量”是可以为0的如果占0格那状态转移时就要特判否则陷入无限循环或者无意义的比较。多数题目不会那么极端但刷题时要保持敏感。3. 实操过程与核心环节实现3.1 P1060“开心的金明”完整代码与逐行注解我直接给出C的AC代码注释写得比较细方便你们对照着理解。#include bits/stdc.h using namespace std; const int MAXN 30005; int dp[MAXN]; // dp[j]表示预算为j时的最大收益 int main() { int N, m; cin N m; for (int i 0; i m; i) { int v, p; cin v p; int value v * p; // 关键把重要度乘上价格作为收益 for (int j N; j v; j--) { dp[j] max(dp[j], dp[j - v] value); } } cout dp[N] endl; return 0; }踩坑点放在这里MAXN要开够。我见过有人开小了提交后部分点WA但本地测试因为数据小一脸懵。P1060的N上限是30000那我直接开30005别抠抠搜搜。收益是v×p不是p。这个看错的话样例就能测出来问题但有些人样例过了因为刚好凑巧所以还是建议做题前在草稿纸上把题意转成数学表达式。内层循环的边界是j v不是j 1或j 0。因为要保证j - v 0不然越界访问数组行为未定义可能随机WA或RE。3.2 P2663“越越的组队”两种状态设计对照这里我给出两种写法的对照其一是朴素二维布尔数组其二是优化后的一维数组。写法一二维布尔数组#include bits/stdc.h using namespace std; const int MAXN 105; const int MAXSUM 10005; int a[MAXN]; bool dp[MAXN][MAXSUM]; // dp[i][j]表示选i个人能否达到总能力值j int main() { int n; cin n; int sum 0; for (int i 0; i n; i) { cin a[i]; sum a[i]; } int half sum / 2; int maxp n / 2; dp[0][0] true; for (int i 0; i n; i) { for (int cnt maxp; cnt 1; cnt--) { for (int val half; val a[i]; val--) { if (dp[cnt - 1][val - a[i]]) { dp[cnt][val] true; } } } } // 找答案从half往下找第一个可行状态就是最大可能 for (int val half; val 0; val--) { bool ok false; for (int cnt 0; cnt maxp; cnt) { if (dp[cnt][val]) { ok true; break; } } if (ok) { cout val endl; return 0; } } return 0; }写法二一维优化#include bits/stdc.h using namespace std; const int MAXN 105; int a[MAXN]; int dp[MAXN]; // dp[j]表示选j个人能获得的最大总能力值 int main() { int n; cin n; int sum 0; for (int i 0; i n; i) { cin a[i]; sum a[i]; } int half sum / 2; int maxp n / 2; // dp[j]初始化为 -infdp[0] 0表示选0个人能力值为0 for (int j 1; j maxp; j) dp[j] -1e9; dp[0] 0; for (int i 0; i n; i) { for (int j maxp; j 1; j--) { if (dp[j - 1] 0) { dp[j] max(dp[j], dp[j - 1] a[i]); } } } int ans 0; for (int j 0; j maxp; j) { if (dp[j] half) { ans max(ans, dp[j]); } } cout ans endl; return 0; }写法一容易理解写法二更省内存。我自己的经验是比赛时如果卡时间卡得紧直接写优化版没毛病如果是学习阶段两种都写一遍能帮你把状态设计想得更透彻。注意写法一里内层循环做了倒序cnt倒序、val倒序这是必要的。如果你把cnt正着遍历同一个同学可能被连续选中好几次人数限制就形同虚设。3.3 P1964“mc生存之卖东西”代码与多重背包拆解这题我需要先把输入抽象的细节说清楚。假设输入格式是总钱数/格子数、物品种类数然后每种物品给出名称、数量、单个价值、占格子数。为了方便处理可以把每种物品先按单价从高到低排个序因为同样占一个格子的物品单价高的显然优先考虑。这一步是贪心的思想但注意它不是简单的贪心题因为同一类物品数量有限且可能占多格所以处理好之后还是得跑多重背包。看下面的核心代码框架#include bits/stdc.h using namespace std; struct Item { int count; // 数量 int val; // 单个价值 int space; // 单个占格子数 }; vectorItem items; int dp[10005]; void zeroOnePack(int space, int value, int C) { for (int j C; j space; j--) { dp[j] max(dp[j], dp[j - space] value); } } void completePack(int space, int value, int C) { for (int j space; j C; j) { dp[j] max(dp[j], dp[j - space] value); } } void multiplePack(Item it, int C) { int k 1; int cnt it.count; // 二进制拆分 while (k cnt) { zeroOnePack(k * it.space, k * it.val, C); cnt - k; k 1; } zeroOnePack(cnt * it.space, cnt * it.val, C); } int main() { // 读入、填充items数组 // C是总格子数 memset(dp, 0, sizeof(dp)); for (auto it : items) { multiplePack(it, C); } cout dp[C] endl; return 0; }这段代码里把01背包、完全背包、多重背包的函数都写出来了通用性很强。二进制拆分那部分值得多说一句当cnt10时第一次取出k1第二次k2第三次k4此时剩余cnt3最后一次直接把3放入01背包。这样组合起来1、2、4、3可以凑出0到10之间的任意数时间复杂度从O(10)降到O(log10)效果显著。4. 常见问题与排查技巧实录这节我讲讲我刷题和给学弟学妹debug时经常看到的问题每一道题都有对应的坑。4.1 P1060常见WA点数组越界、收益写错、循环顺序颠倒数组越界是最大杀手。N为30000dp开30005一般没问题。但有些人的上限习惯写成N1导致最后一轮更新时dp[j-v]出现负下标如果编译器不报错很可能出现一个莫名其妙的随机值最终答案跟标准答案差距很离谱而不是“差一点”。收益写错也很常见。有些人写成了dp[j] max(dp[j], dp[j-v] p)忘乘v导致样例过、但提交WA。建议在草稿阶段就把“价格×重要度”定义成一个变量避免混用。循环顺序颠倒外层必须遍历物品内层必须倒序遍历容量。如果不小心把内层变成顺序遍历相当于无限次拿同一物品跑出来你会很“开心”地用200块的预算买出远超预算的总价然后还觉得自己没写错。4.2 P2663常见WA点人数维度当物品、答案区间的选择P2663最大的坑在于把人数限制落在状态里时写错了维度方向。比如有些人写for (int i 0; i n; i) { for (int j 1; j maxp; j) { dp[j] max(dp[j], dp[j - 1] a[i]); } }这里j正序内层循环遍历人数表面看着没问题但当你以后更新dp[2]时dp[1]可能已经用过了当前这个人于是同一个同学被算了两遍。正确写法是把j也倒序。我在debug时经常看到的错误代码十有八九是这里。答案区间的选择也值得注意。有人直接在找答案时写了if (dp[j] half) ans max(ans, dp[j])这个逻辑是对的但前提是dp[j]不能是负数。所以初始化时不能把所有dp都置0而要把dp[0]0其余置为负无穷或一个很小的负数。否则当某个j人数不可达时dp[j]为0你会以为选j个人能力值为0是合法的最终答案可能出现偏差。4.3 P1964常见WA点二进制拆分边界、物品排序误区P1964里比较普遍的误区是对物品按单价排序后直接贪心选取不再做背包。这种贪心在格子数为1的情况下是正确的因为所有物品都占1格选单价最高的几个即可但一旦格子数不同贪心就失灵了。比如A物品单价5但占2格B物品单价4但占1格格子数为2时选B两个得到8选A一个才5贪心会选A但实际最优是B。所以排序只能用于优化搜索顺序不能替代背包DP。二进制拆分的边界条件也要小心。很多人写while循环时k cnt的写法在不同教材里略有不同。我上面的写法是每次取kcnt减去kk左移一位循环结束后把剩下的cnt作为一个新物品。这个写法的核心在于当剩余cnt小于k时后面的一次性zeroOnePack(cnt * it.space, cnt * it.val, C)刚好补齐所有不足的部分覆盖完全。我曾见过有人写while (cnt 0)然后在循环里k1最后导致拆分出的物品数量超过实际数量选出来的结果超过了物品真实库存。这本质上是对二进制拆分原理的理解不到位。建议自己拿纸笔手算几组数据比如数量为14拆成1、2、4、7看看能不能组合出1到14的所有数量。5. 刷题路径与扩展思考三道题之后的背包体系这三道题做完我强烈建议你趁热打铁把背包问题的几个经典变种都过一遍形成自己的知识网络。5.1 背包九讲中的相关模型串联背包问题里除了01背包、完全背包、多重背包之外还有混合背包、二维费用背包、分组背包、依赖背包树形背包等。P1060是01背包的入门题。P2663可以当作二维费用背包的简化版一维费用是人数一维是能力值。P1964是多重背包恰好可以用二进制拆分解决。下一步可以按这样的顺序刷P1048“采药”纯01背包练手P1616“疯狂的采药”完全背包入门P1776“宝物筛选”多重背包而且数据范围比P1964更大对二进制拆分的必要性体会更深P1855“榨取kkksc03”二维费用背包经典P2014“选课”依赖背包/树形背包如果学有余力再碰这么串下来背包问题的基础框架基本就焊死在脑子里了。5.2 从“模板题”到“变式题”的思考方式我见过不少人刷题有个毛病只看题解背模板P1060过了就以为自己会01背包了结果遇到P2663这种套了个“人数”限制就懵了。这说明没抓住背包问题的本质——状态就是“限制条件”的集合。题目给你多少种限制预算、人数、数量、格子、时间……状态就开多少维或者压缩成若干维的数组转移时把所有限制当作容量逐个倒序遍历。想通这一层很多看似新题的老题其实都是一个套路。我给新人推荐一种练习模式拿到一道背包变式题后先用纸笔写出有什么限制每个限制的“容量”是多少每个物品的“体积”是什么“价值”是什么状态定义用哪几个维度空间能否压缩写明白这三点再动键盘正确率能翻一倍。这也是我从P1060一路刷到P1964之后再看到任何背包题都心里不慌的原因。6. 总结一下我个人实操中的体会这三道题我前前后后用不同语言写过很多遍C、Java、Python都有。直观感受是语言不是瓶颈状态设计才是。如果非要说一个最重要的关键点那就是循环顺序。01背包的逆序容量多重背包的二进制拆分P2663里人数维度的逆序——只要有一个循环方向写错答案就会偏离而且这种错误往往很难通过样例发现因为小数据下有时巧合能蒙对大数据下就原形毕露。还有一个常用技巧输出中间过程。比如P2663你在循环结束后把dp数组打出来看看每个j对应的最大值是否符合直觉能帮你快速定位是不是循环顺序写错了。我以前写背包题时如果不确定自己的转移方向有没有写反就打印一遍dp数组立刻清楚。三道题串起来看代码总量不大但背后的建模思想很值钱。希望这篇题解能让你少走点弯路也欢迎你有更妙的做法来交流。