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

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

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

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

【考点】贪心算法｜算法适用性

🎯 考纲定位：GESP 五级 算法模块，考察贪心策略的适用范围。命题人专门挖了个坑：学生背了“贪心求最优”的结论，却不知它只在具备最优子结构且贪心选择性质时才成立。这道题卡住的是“只记结论、不懂前提”的短板，属于五级基础算法模块的典型陷阱题。

🧠 解题思维：看到“贪心一定全局最优”这种绝对化表述，第一反应就是找反例。贪心算法的核心是“每一步选当前最优”，但这只能保证局部最优，无法保证全局最优。比如经典的 0/1 背包问题，若按价值密度贪心选，往往错过组合最优解，必须用动态规划。所以，贪心算法能解的问题有严格前提（最优子结构+贪心选择性质），不满足前提时，贪心必错。

🪤 陷阱拆解：A 选项是命题人精心设计的“绝对化”陷阱。学生若只背了“贪心算法用于求最优解”的结论，看到“一定”就判断为正确。但命题人特意把“一定”放在句子里，就是为了卡住“只记结论、不懂前提”的学生。这道题最阴险的细节在“一定”二字——它把局部最优强行等同于全局最优，忽略了贪心算法成立的前提条件（最优子结构、贪心选择性质），是五级考试里专门用来检测学生是否真正理解算法本质的检测点。

🔄 反命题思维：如果把“一定”改成“有时能”，答案就变了——贪心算法确实有时能解最优。如果把问题换成“分数背包”，贪心就能正确求解。如果把问题换成"0/1 背包”，贪心就会错，必须用动态规划。命题人想考的是“贪心算法的适用范围”，而非“贪心算法的定义”。