GESP 五级 · GESP 202412 C++ 五级 第 19 题

贪心算法通过每一步选择当前最优解，从而一定能获得全局最优解。

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

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

【考点】贪心算法特性｜算法正确性证明｜绝对化表述陷阱

---

🎯 考纲定位 GESP 五级算法模块，命题人卡住的是学生把"贪心"想成"万能钥匙"的认知偏差——五级考生刚接触贪心策略，容易望文生义，以为贪心=最优解，这道题就是专门检验你是否真正理解贪心的本质局限。

🧠 解题思维 看到"贪心算法"四个字，先要反应出它的核心定义：每一步局部最优选择。但局部最优≠全局最优，这是贪心算法的先天缺陷。命题人把"一定能获得全局最优解"这种绝对化表述放在正确答案里，就是在测试你是否能识别出这个逻辑断层。正确思维链是：贪心策略→局部最优选择→对某些问题有效→对另一些问题失效→不能保证全局最优。

🪤 陷阱拆解 "一定能"三个字是本题最阴险的绝对化表述，任何正规算法都不可能保证对所有问题都得到最优解。命题人利用的是学生刚学完贪心例子（如哈夫曼编码、活动选择）产生的"幸存者偏差"——那些成功的例子让学生误以为贪心万无一失。如果你只记住了贪心能解决的问题类型，却没理解它何时失效，就会掉进这个绝对化表述的坑里。

🔄 反命题思维 改一个条件就变真题了：把"一定能"改成"可能"，或者加上前提"当问题具有贪心选择性质时"。刷到类似题先问自己：这个算法对所有情况都成立吗？有没有反例？