GESP 五级 · GESP 202509 C++ 五级 第 25 题

贪心算法总能得到全局最优解。

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

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

【考点】贪心算法最优性条件｜逻辑陷阱识别

本题位于 GESP 五级“算法模块”核心考点，专门针对“贪心策略适用性”设计。命题人利用考生对“局部最优”与“全局最优”关系的模糊认知，卡住大量只会背诵定义却不懂适用边界的选手——他们知道活动选择问题能用贪心，却误以为所有贪心都成立。

解题时先锁定关键词“总是”，这是绝对化表述。回忆贪心算法本质：每一步选择当前最优解，但未必保证整体最优。经典反例如 0/1 背包问题，贪心按价值密度排序可能忽略体积限制，导致总价值非最大。因此，当看到“总是”类断言时，应立即启动反例搜索思维，这是处理此类概念判断题的通法。

错误选项 B 看似反直觉，实则精准打击“以偏概全”思维。命题人故意省略“在某些问题中”这一限定词，制造了语义陷阱——考生若只记住“贪心能解决活动选择问题”等成功案例，就会误判为 A。这揭示了训练中的致命弱点：缺乏对算法适用条件的系统性理解，仅凭经验记忆做题。

若将题干改为“某些贪心算法总能得到最优解”，答案即为 A；若限定“所有贪心算法”，则 B 成立。刷到类似题时，务必先问自己：这个算法对什么问题有效？为什么有效？这才是摆脱陷阱的根本方法。