GESP 五级 · GESP202609 C++ 五级 第 24 题

下面的贪心代码一定能对任意硬币面值集合 coins 求出 money 所需的最少硬币数。

int count = 0;

for (int coin : coins) { // coins 按面值从大到小排列

count += money / coin;
money %= coin;
}

这题一眼看出是贪心策略，但贪心不是万能钥匙。看到"任意硬币面值集合"这个表述，立刻警觉——命题人就是要考你贪心算法的适用边界。硬币找零问题有经典反例，比如面值{1,3,4}凑6元时贪心取4+1+1=3枚，最优解是3+3=2枚。解题关键不是验证代码语法，而是构造反例证伪。

选A的考生往往陷入两个误区：一是被"按面值从大到小排列"这个条件迷惑，以为排序就能保证最优；二是只想到标准货币体系（1,5,10,25）中贪心确实成立，就过度推广。代码本身完全正确，但贪心策略对任意面值集合并不成立——这是概念混淆的典型陷阱。

1. 考纲定位

本题考查《GESP 考试大纲》五级算法模块中的贪心策略。命题人放这道题，就是要卡住"贪心万能论"这个认知盲区——绝大多数考生看到贪心代码就默认正确，却不知贪心只在特定条件下（如标准货币体系）才保证最优解。

2. 解题思维

看到"任意硬币面值集合"，立刻想到硬币找零的经典反例。构造面值{1,3,4}、目标金额6：贪心算法依次取4（余2）、3（取0个）、1（取2个），共3枚；但最优解是3+3=2枚。这个反例足以证伪"一定能求出最少硬币数"。通法是：对贪心类题目，先找反例，再谈证明。