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

贪心算法的解可能不是最优解。

这题考贪心算法的本质——局部最优不等于全局最优。拿到题先别想具体题目，直接联想反例：找零问题面额{1,3,4}凑6，贪心选4+1+1得3枚，最优是3+3得2枚，这就证伪了‘贪心一定最优’。

很多学生死记‘贪心=最优解’的口诀，看到题干说‘可能不是’就下意识选B，觉得命题人在绕弯子。其实命题人就是卡这个思维定式，用‘可能’二字留了理论空间，诱导只背结论的人误判。典型错误是把‘某些贪心问题有最优解’偷换为‘所有贪心问题都保证最优解’，忽略了反例的存在。

【考点】贪心策略的局限性｜反例构造法

考纲定位：GESP五级算法模块常考‘策略局限性’判定，命题人借‘可能不是最优解’这句话卡住大量只背‘贪心=最优’口诀的考生，考察对算法本质而非表面结论的理解。这类题在近年考频明显上升，2024年16题、2025年12题、2026年24题，合计52题，占比超七成，说明命题趋势是越来越喜欢用‘绝对化断言’设陷阱。

解题思维：看到‘贪心可能不优’应立刻联想反例构造法——先确认贪心局部最优≠全局最优的数学事实，再在头脑中构造一个具体场景（如找零问题：面额{1,3,4}目标6，贪心选4+1+1得3枚，最优为3+3得2枚），此类题通法是‘理论断言→反例验证→结论确认’，属于算法证明类题型的标准路径。

陷阱拆解：选项B‘错误’诱导人认为贪心必优，这是把‘某些贪心问题有最优解’偷换为‘所有贪心问题都保证最优解’的典型语义陷阱；题目用‘可能不是’而非‘一定不是’，说明命题人故意留了理论上的例外空间，若只靠死记结论必会误选B。反命题思维：若把题干改成‘贪心算法总能得到最优解’，答案必为B，反例仍是找零问题；若改成‘动态规划能保证最优解’，考点就迁移到状态转移方程与最优子结构。刷到任何绝对化算法断言时，先问自己‘是否有反例’才是破题关键。

考频趋势：贪心算法在题库共考过71题，覆盖9个考试级别（2010-2026），其中2024年16题、2025年12题、2026年24题，合计52题，占比超七成，说明命题趋势是越来越喜欢用‘绝对化断言’设陷阱。GESP五级25题、六级13题、CSP入门级12题，五级仍是重灾区，考生需警惕此类概念辨析题。

预测：基于2024-2026年数据，未来GESP五级、六级及CSP入门级仍会高频出现‘算法局限性’类判断题，命题人可能继续用‘可能不是’‘一定不是’等模糊表述挖坑，甚至结合具体场景（如活动选择、区间覆盖）要求判断贪心是否适用。暂无足够依据预测具体题型变化，但‘反例思维’将是必考能力。