GESP 六级 · GESP 202406 C++ 六级 第 25 题

对 0-1 背包问题，贪心算法一定能获得最优解。

贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。

贪心算法需要严格证明正确性。典型错误：局部最优不等于全局最优。例如0-1背包问题就不能用贪心。

【考点】0-1 背包问题｜贪心算法｜反例证明

🎯 考纲定位 本题考查《GESP 大纲》算法模块中 0-1 背包问题与贪心策略的本质差异，卡住的是那些只背结论、不验证反例的考生。命题人专门在六级放这道判断题，就是要筛掉把"贪心=最优"当万能钥匙的学生。

🧠 解题思维 看到"贪心一定最优"，第一反应是反例验证。0-1 背包的经典反例：物品1(重2价值3)、物品2(重3价值4)，容量5。贪心选物品1(价值3)，剩容量3只能选物品2(价值4)，总价值7；若选物品2(价值4)，剩容量2选物品1(价值3)，总价值7。看似相等，但调整数值即可打破平衡，如物品2改为重3价值5，贪心选1总价值8，选2总价值5，贪心反而更优。

🪤 陷阱拆解 命题人用"一定能"这种绝对化表述设坑。如果你只背"贪心求最优解"而不理解0-1背包的离散性，就会掉进这个陷阱。贪心对分数背包有效，因为可以拆分物品；但对0-1背包无效，因为每个物品要么全取要么不取，局部最优无法保证全局最优。

🔄 反命题思维 反命题视角：若题目改为"分数背包"或"最大化物品数量"，贪心可能成立。这提醒我们：刷到类似题先问"命题人想考我什么"，是算法的适用边界，不是万能钥匙。