1. 题目到底在说什么1.1 先把题意拆明白P2240 是洛谷“深入浅出基础篇”题单里第 12 章“贪心算法”的第一道例题题目名字叫“部分背包问题”。看到“背包”两个字很多初学者第一反应就是动态规划里的 01 背包但这里的“部分”二字是整个题目的灵魂。题目的大致描述是这样的有一个背包容量给你一个上限然后给你若干种物品每种物品有重量和价值但关键点在于——每种物品可以只取一部分。比如一件物品总共 10 千克价值 100 元你可以只拿 2 千克对应的价值就是 20 元。也就是说物品是“可分”的不像 01 背包里每件东西只能要或者不要。输入格式一般是第一行两个整数表示物品数量 n 和背包容量接下来 n 行每行两个整数分别表示物品的重量和价值。输出要求是背包能装下的最大总价值通常保留两位小数。为什么会有小数因为一件物品可能只取了一部分算出来的价值自然就是小数。我第一次看到这道题的时候脑子里冒出来的想法是这有什么好贪心的直接按照性价比排序不就完了吗后来才发现能一眼想到这个并写对代码本身就是理解贪心算法的关键一步。这道题放在深基第 12 章的第一题目的就是让初学者用最直观的方式建立“贪心策略”的印象。1.2 背包问题的家族谱系要真正理解这道题必须把它放在背包问题的谱系里看。背包问题家族有好几个成员01 背包、完全背包、多重背包、分组背包还有这道题涉及的部分背包。01 背包的典型场景是n 个物品每个物品只能拿一次容量有限求最大价值。这种问题用动态规划解因为每个物品的“不可分割性”导致局部最优不一定能推出全局最优。比如有两个物品一个重 5 价值 6一个重 4 价值 5背包容积 8如果只按性价比选你会选第二个性价比 1.25比第一个的 1.2 高但剩下的 4 容量装不下任意物品总价值只有 5而如果选第一个剩下的 3 容量同样装不下什么总价值反而是 6。你看在 01 背包里性价比贪心直接翻车。但部分背包不一样物品可以切分所以容量总能被完全利用除非所有物品都装完了背包还有剩余。切分之后每一单位重量的价值是恒定的那么优先拿单位价值最高的单位重量自然就是最优策略。打个比方你去超市买散装坚果价格按单价计算你手里的钱有限你会先挑单价最贵但自己最喜欢的品种吗不会你一定会先称单价最高的那种因为同样一笔钱买单价高的东西获得的“总满足感”最大。这就是贪心直觉的核心。P2240 这个“深基”题单从顺序表、链表一直讲到栈、队列、树和图第 12 章专门讲贪心而部分背包是贪心算法里面“最优子结构”最明显的入门案例。弄懂这一题后面再做“合并果子”“区间调度”之类的问题思路会顺畅很多。2. 核心思路为什么是贪心而不是动态规划2.1 一个生活化的直觉先做一个思维实验。假设你的背包容量是 10 千克面前有三种物品物品 A重 6 千克价值 12 元单价 2 元/千克物品 B重 4 千克价值 10 元单价 2.5 元/千克物品 C重 5 千克价值 15 元单价 3 元/千克如果你按总价值从高到低拿会先拿 C再拿 A但 A 需要 6 千克剩下的 5 千克不够你只能拿 A 的 5 千克价值 10 元总共 25 元如果按单价从高到低拿先拿 C再拿 B容量刚好用完总价值 15 10 25 元结果一样。但换个数据比如背包容量是 8 千克按总价值拿是 C5 千克加上 A 的 3 千克价值 6 元一共 21 元按单价拿还是 C 加 B一共 25 元。看出来了吗按单价拿永远不亏因为当你把容量分给“便宜”的单位时等于浪费了本该给“更贵”单位的机会。这个道理在日常生活中其实就是“把钱花在刀刃上”。选择单价最高的物品先装相当于把有限的容量分配给单位价值最高的部分然后再分配给次高的直到容量用完。这种每一步都选择当前看起来最优的方案就是贪心。而部分背包恰好满足“每一步的局部最优能推出全局最优”因为同一件物品的任何一部分都是完全等价的不存在“选了一件就必须放弃另一件”的约束。2.2 正确性证明的直观理解很多教程在讲贪心时喜欢直接跳过证明但这道题恰恰是理解“贪心为什么有效”的最佳样本。可以用交换论证来想。假设有一个最优方案在某个单位容量里装的是某一物品中单位价值为 v1 的一部分而同时另一件单位价值更高v2 v1的物品反而没装或者只装了一部分。那我把这单位容量里的 v1 换成 v2总价值会变大这跟“最优”矛盾。所以最优方案一定会优先装单位价值最高的物品直到装满。再换一个角度。因为物品可分我们可以把每件物品拆成若干个“1 千克小包”每个小包的价值就等于它的单价。这样一来问题就变成了在一个装了很多小包的袋子里每个小包有各自的重量都是单位重量和价值容量有限选哪些小包当所有小包重量相同、价值不同时按价值从高到低选当然是最大价值——这甚至不需要“贪心证明”而是显然的。这也是为什么部分背包问题不需要动态规划。动态规划的成立需要“无后效性”和“重叠子问题”部分背包确实也满足这些条件但它还有个更强的性质——贪心选择性质即每一步的局部最优选择永远可以出现在某个全局最优解中。有了这个性质我们直接用贪心就能在线性扫描里解决没必要开二维数组做 DP。2.3 与 01 背包的分水岭在哪理解了这个再看 01 背包和部分背包的区别就非常清晰了。01 背包里你面对一个价值很高的物品但它的重量大于剩余容量对不起装不下就是装不下你不能拆开。所以你需要考虑“装 or 不装”的决策要用状态转移来枚举所有可能性。部分背包里没有这种“非黑即白”的决策只有“装多少”的问题。既然可以拆就默认你永远不会浪费容量除非所有物品都装完了但背包还有剩余。这种情况下按性价比排序的贪心是天然正确的。我在实际写代码的时候会把这道题和 01 背包的模板题放在一起对比着刷目的就是加深印象看到“可以分割”马上想到贪心看到“不可分割”马上想到 DP。这种条件反射不是靠背而是靠对比着理解理解得越深做题越快。3. 具体实现步骤与 C 代码3.1 数据结构和排序的设计实现这道题的第一步是选对数据结构。每种物品有重量、总价值两个属性还要计算单位价值写三个数组当然可以但用结构体把所有属性打包在一起更清晰。尤其后面要排序用结构体排起来方便得多。结构体可以这样定义struct Item { double weight; // 重量 double value; // 价值 double ratio; // 单位价值即 value / weight };重量和价值在题目里通常给的是整数但计算单位价值之后是浮点数所以直接用 double 存储更方便也避免后面类型转换的麻烦。排序用 sort 函数第三个参数传一个自定义比较函数按照 ratio 从大到小排列bool cmp(Item a, Item b) { return a.ratio b.ratio; }这里有个细节sort 的比较函数里返回 true 表示 a 应该排在 b 前面。我们要的是“单位价值高的排前面”所以当 a.ratio 大于 b.ratio 时返回 true也就是降序排列。很多初学者会写成 return a.ratio b.ratio结果排成升序这个问题我后面单独列一节讲。排序之后整个核心逻辑就很简单了从头开始遍历排好序的物品数组如果背包剩余容量装得下当前物品就整件装进去装不下就只装剩余容量对应的部分然后 break 退出循环因为背包已经满了。3.2 完整可运行的代码这里给出一个完整的 C 实现方便直接复制调试#include iostream #include algorithm #include iomanip using namespace std; struct Item { double weight; double value; double ratio; }; bool cmp(Item a, Item b) { return a.ratio b.ratio; } int main() { int n; double capacity; cin n capacity; Item items[1005]; for (int i 0; i n; i) { cin items[i].weight items[i].value; items[i].ratio items[i].value / items[i].weight; } sort(items, items n, cmp); double totalValue 0.0; for (int i 0; i n; i) { if (capacity items[i].weight) { // 整件装入 capacity - items[i].weight; totalValue items[i].value; } else { // 只能装入一部分 totalValue items[i].ratio * capacity; break; } } cout fixed setprecision(2) totalValue endl; return 0; }这段代码本身并不难但它包含了几个关键点结构体定义、自定义排序、浮点数累加、以及“容量不足时按比例折算”的边界处理。缺了任何一个环节结果都有可能是错的。3.3 逐行拆解关键细节先看排序那一段。sort 的区间是左闭右开的所以写 sort(items, items n, cmp)意思是把数组 items[0] 到 items[n-1] 全部排序。如果你用的是 vector就写 sort(items.begin(), items.end(), cmp)效果一样。再看循环里的分支。如果背包剩余容量大于等于当前物品的总重量说明可以整件拿走直接把容量减掉价值加上总价值。这种情况下我们不需要处理每一“部分”因为整件拿走就是最省事的操作。如果剩余容量小于当前物品的重量说明当前物品只能拆开装装多少装“剩余容量”那么多也就是 capacity 千克。这部分的价值等于单价乘以重量也就是 ratio * capacity。装完之后背包剩余容量归零循环必须 break否则后面还会尝试装下一个物品但容量已经是 0 了再走下去只是浪费时间而且可能因为浮点数误差导致一些奇怪的问题。有些人会问如果容量剩余 0循环继续走会怎样if 判断里 capacity items[i].weight 肯定不成立容量为 0重量为正数else 分支里会累加 ratio * 0也就是 0然后 break。所以理论上不 break 也不影响最终答案。但从代码规范和效率角度讲明确写 break 更好因为它表达了“背包已满不需要再看后面的物品”这个逻辑可读性更强。3.4 复杂度分析这道题的时间复杂度由两部分组成排序和遍历。排序用的是 sort平均时间复杂度为 O(n log n)遍历一次物品数组时间复杂度为 O(n)。所以总体时间复杂度是 O(n log n)。空间复杂度为 O(n)主要用来存储 n 个物品的结构体。这个复杂度非常理想即使 n 达到 10 的 5 次方甚至更大也能在 1 秒左右跑完。对比一下 01 背包的动态规划解法时间复杂度是 O(n*capacity)其中 capacity 是背包容量。如果 capacity 很大比如 10 的 9 次方DP 直接无法进行但部分背包的贪心解法完全不受容量大小影响因为容量只参与比较不参与数组维度。这也是部分背包问题的天然优势。4. 常见错误与调试实录4.1 排序方向反了这是所有初学这道题的人最常犯的错误。按照性价比降序排列比较函数应该是 return a.ratio b.ratio。如果写成了 return a.ratio b.ratio排序结果就是单位价值最低的排在最前面那么先装的就是最“便宜”的东西。等便宜的都装完了如果背包还有容量再装贵的总价值往往不是最优甚至差得很远。这种错误在样例数据上有可能“骗过”用例。如果测试数据里所有物品单价都是一样的不管升序降序结果都一样但正式评测数据肯定不是这么准备的。我自己的调试经验是先用一个简单的样例手算一遍比如上面第 2 节提过的 8 千克背包的例子然后看程序输出是否和手算一致。一旦发现输出大于正确答案那多半是排序方向错了。4.2 浮点数类型使用不当题目中物品的重量和价值输入是整数但如果定义结构体时全用 int计算 ratio value / weight 时会触发整数除法得到的结果是整数比如 3 / 2 1而不是 1.5。这种精度损失会在累加价值时被放大最终输出的结果错得离谱。另一个容易踩的坑是输出格式。题目要求保留两位小数输出 25.00 而不是 25所以要用 fixed setprecision(2) 控制格式。如果忘了加 fixedsetprecision(2) 控制的是总有效数字位数而不是小数位数25 会输出成 25因为有效数字位数只要 2 位就足够表示而不是 25.00。虽然数值上等价但格式不对照样判错。4.3 边界情况没想清楚边界情况主要分三种背包容量为 0、所有物品重量之和小于等于背包容量、以及容量介于两者之间。容量为 0 的场景比较极端正常评测可能不出现但程序要能正确处理。遍历时每个 items[i].weight 都大于 0所以 capacity items[i].weight 完全不成立会进入 else 分支累加 ratio * 0结果 0然后 break。输出 0.00逻辑没问题。所有物品都装得下的情况循环会完整跑完 n 次每次进入 if 分支capacity 最终变成 0 或者大于 0如果所有物品总重量小于背包容量。这时候 totalValue 就是所有物品价值之和也没问题。注意此时如果 capacity 还有剩余说明装完了所有物品也没装满背包这是合法的。真正容易出错的是“刚好装满”的情况。假设剩余容量等于当前物品重量if 判断 capacity items[i].weight 成立会把整件装进去capacity 变成 0循环继续。这时下一个物品会进入 else 分支累加 0 然后 break。代码能正确处理但如果你在 else 分支里写了“只装入部分”的逻辑而忘记处理刚好相等的情况可能把整件物品拆成两部分虽然数学上结果一样但写法不够漂亮。建议把 和 分开看 的处理是最稳妥的。4.4 常见问题速查表问题现象可能原因解决方法输出结果比预期大很多排序用了升序把 cmp 中 改成 的写法反过来输出结果比预期小很多某些物品没被装入检查是否用了 int 存 ratio改成 double输出 25 而不是 25.00忘了 fixed使用 cout fixed setprecision(2)程序运行超时复杂度太高确认没有在循环里再嵌套排序小样例正确、大样例错误浮点数累加误差累加时用 double不要来回转 int答案总是少了最后一个物品的部分价值循环内缺少 breakelse 分支处理完部分价值后必须 break这个速查表是我在实际调试里一点点攒出来的经验尤其是最后一条“少了部分价值”我第一次写的时候确实漏了 break导致部分装入的物品算完之后还把后面物品的 ratio * 0 当成 0 加上去看着没错但逻辑上是绕了一圈。后来理清思路发现 break 是必须的。5. 从 P2240 延伸出去的思考5.1 “深基”题单的学习路径P2240 是洛谷“深入浅出基础篇”题单里的一道经典题这个系列在 OI 圈子里被叫成“深基”题号通常带有“深基”字样。第 12 章是贪心《部分背包问题》是这章的第一道例题后面的题会逐渐增加难度比如“合并果子”要用优先队列“区间覆盖”要按右端点排序。这些都是贪心算法的不同应用场景。很多初学者刷题时有一个误区只追求 AC不注重理解。我看到不少人在评论区分享代码70 分、80 分就发帖求助贴的代码只差一个 cmp 函数的方向就能满分。这说明他们已经理解了“要排序”但对贪心策略的核心——为什么这样排序是对的——没有真正吃透。做 P2240 这道题我建议每写完一版代码都手动模拟一遍排序过程画出数组的变化再拿几组自造数据验证。这个过程比 AC 本身更值钱。深基题单后面还有顺序表、链表等章节比如热搜里提到的 P3156【深基15.例1】询问学号是顺序表相关的内容。P3156 和 P2240 看起来风马牛不相及但它们都在训练一个共同的能力根据数据特点选择合适的数据结构与算法。P3156 里用数组存学号直接按下标查询是 O(1) 的P2240 里用结构体存物品按单价排序是 O(n log n) 的。这两种选择都不是随意来的而是分析题目需求后得到的最优解。5.2 变体与进阶思考部分背包问题看似简单但改一改条件就能变成新的问题。比如如果每个物品不仅要考虑重量和价值还有一个“数量上限”每种物品最多只能装 k 千克那仍然是贪心只是需要把“能装多少”改成“min(k, 剩余容量)”逻辑上还是要先按单价排序。再比如把“每个物品可分割”改成“每个物品可变价”也就是买得越多、单价越低阶梯计价问题性质就完全不同了。这时候简单的性价比排序失效因为单价会随购买量变化你可能需要在“大量买便宜的”和“少量买贵的”之间权衡这就变成更复杂的优化问题也许要用到动态规划或者数学建模。还有一个很经典的变体是“带惩罚的部分背包”背包里每单位容量都有一个基础价值如果装入的物品单位价值低于某个阈值不如直接空着。这时候贪心策略依然先按价值排序只是在选择时加入阈值判断。这种变体在竞赛题里偶有出现但核心思想不变理清楚决策变量使用正确的最优化策略。我个人在刷 P2240 之后还会自己造几组数据故意让某些物品重量相同但价值不同或者让背包容量刚好等于某几个物品的重量之和检验贪心结果是否和手算一致。这种额外的测试能在很大程度上帮助理解“贪心选择性质”的边界——什么情况下贪心一定对什么情况可能出错。5.3 一个可以自己动手做的小实验这里分享一个我当初学习贪心时用过的小方法。随手写一个暴力枚举的程序用 dfs 模拟所有分发方式再写一个贪心的程序然后随机生成数据让两个程序跑同样的输入比较输出是否一致。如果一致说明贪心策略没有明显错误如果不一致就打印出差异数据分析贪心错在哪里。这种“对拍”技巧在 OI 刷题里非常实用尤其适合验证贪心类的题目。P2240 本身因为知道贪心是对的不需要对拍但用对拍去验证更复杂的贪心题比如区间问题时效率非常高。以后刷到一道贪心题如果心里没底写个暴力程序对拍很快就能发现逻辑漏洞远比盯着屏幕发呆强。我自己的习惯是写完一份代码之后再写一份复杂度更高但一定正确的暴力版本随机生成几千组小数据两个程序同时跑。只要有一组不一致就用那组数据去调试直到完全一致。这个方法帮我省下了大量 debug 时间强烈推荐给你。6. 这道题带给我的实战体会刷了这么多题之后回头看P2240 最大的价值不是教会你怎么写一个排序加循环而是帮你建立两个思维习惯。第一个习惯是“先问能不能贪心再想怎么贪”。拿到任何最优化问题先判断是否存在贪心选择性质如果能找到反例果断放弃贪心考虑 DP如果一时找不到反例再用数学推导或者对拍去验证。第二个习惯是“写代码前先想清楚边界”。这道题里的容量不足时只装部分、装完后 break、浮点输出格式任何一个细节不注意都可能丢分。如果让我给初学者一个建议我会说不要急着提交先把样例在纸上完整模拟一遍。把每个物品的重量、价值、单价列成表按单价排序后一步一步地加减容量和价值得到最终答案。然后再看代码一行一行地对照确保代码的逻辑和手算过程完全对应。这个过程看起来费时间但对培养算法思维特别有帮助。另外也可以把这道题和“排队接水”“合并果子”这类其他贪心题放在一起研究找出它们的共性都是某种形式的“局部最优推出全局最优”但具体的排序关键字、决策策略不同。对比着刷对“贪心”的理解会提升得很快。P2240 作为深基体系中的一道基础题后面还有更多的题目等着你去解开。