GESP 五级 · GESP 202606 C++ 五级 第 21 题

贪心算法只要每一步选择当前最优解，就一定能得到全局最优解。

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

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

【考点】贪心策略｜反例构造｜算法正确性条件

本题在 GESP 五级算法模块中定位，命题人专门设计此题卡住大量只背定义的考生——他们误以为贪心法"万能"，实则忽略了其成立必须依赖最优子结构、贪心选择性质等严格前提。

解题思维链：看到"只要……就……"的绝对化表述，第一反应应是"是否所有问题都适用？"。反例构造是破题关键：背包问题中，若按价值密度贪心选品，可能错过整体最优组合；而活动选择问题才真正满足贪心条件。由此提炼通法：贪心算法并非对所有问题都有效，必须验证问题是否具备贪心选择性质和最优子结构性质，否则局部最优未必导向全局最优。

陷阱拆解：选项 A 错在将贪心法适用范围无限扩大。命题人利用"贪心"一词的模糊性，诱导考生只关注"局部最优"表象，却忽略其背后的结构性要求。若考生仅凭"贪心法在多数问题中表现良好"的经验作答，就会掉进这个绝对化表述的陷阱。

反命题思维：若将题干改为"对于具有最优子结构和贪心选择性质的问题，贪心算法一定能得到全局最优解"，则答案变为正确。刷到类似题时，先问自己"命题人是否在测试我对贪心算法适用条件的理解？"