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

使用贪心算法解决问题时，每一步的局部最优解一定会导致全局最优解。

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

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

【考点】贪心算法｜最优子结构｜动态规划

【考纲定位】本题对应 GESP 五级"算法设计"模块中关于贪心策略适用性的核心概念。命题人特意用绝对化表述卡住那些只背"贪心算法能解决问题"却不懂适用前提的考生——五级这个节点，很多学生刚学会写贪心代码就误以为它万能，这道题就是专门纠正这个认知偏差的"清醒剂"。

【解题思维】看到"贪心算法一定全局最优"这个表述，第一反应是"太绝对了"。贪心算法的本质是每次选局部最优，但局部最优能拼成全局最优的前提是问题具有"贪心选择性质"和"最优子结构"，这两点必须题目本身保证，而不是算法自带。就像动态规划一样，贪心也有适用范围：有些问题贪心解最优，有些必须用动态规划或回溯。所以这题不是考你写贪心代码，而是考你理解贪心的边界。

【陷阱拆解】选 A 的人多半是记住了"贪心算法"几个字，没细想"一定"这两个字。命题人就把"总是"换成"一定"，把"可能最优"偷换成"必然最优"，这是典型的偷换概念。还有个隐蔽坑：有些题目贪心能解，但解法叫"动态规划"（比如背包问题用贪心只是近似），而有些贪心解的问题（如区间调度）反而不会要求你写 DP。如果你只背结论不抠定义，就会把两种算法混为一谈，掉进这个坑。

【反命题思维】命题人要是把"一定"改成"可能"，这题就变成"判断贪心算法能否解决某类问题"，需要你具体构造反例；要是改成"某类问题能用贪心解决"，那就要你证明贪心选择性质。下次刷到类似题，先别急着下结论，问自己：这题到底在考贪心的定义，还是贪心的适用范围，还是贪心与其他算法的区别？