GESP 五级 · GESP 202506 C++ 五级 第 13 题

硬币找零问题中要求找给客户最少的硬币。coins 存储可用硬币规格，单位为角，假设规格都小于 10 角，且一定有 1 角规格。amount 为要找零的金额，约定必须为 1 角的整数倍。输出为每种规格及其数量，按规格从大到小输出，如果某种规格不必要，则输出为 0。下面是其实现代码，相关说法正确的是（ ）。

const int MAX_COINS = 10;
int result[MAX_COINS] = {0};  // 假设最多10种面额

int find_coins(const vector<int>& coins, int amount) {
    sort(coins.begin(), coins.end(), greater<int>());

    int n = coins.size();

    for (int i = 0; i < n; ++i) {
        int coin = coins[i];
        int num = amount / coin;
        result[i] = num;
        amount -= num * coin;
        if (amount == 0) break;
    }

    cout << "找零方案如下：" << endl;
    for (int i = 0; i < n; ++i) {
        cout << sorted_coins[i] << "角需要" << result[i] << "枚" << endl;
    }

    return 0;
}

仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】贪心算法｜算法最优性分析｜排序的应用

1. 🎯 考纲定位

本题考查《GESP 考试大纲》五级"算法基础"模块的贪心算法识别能力。命题人专门设计这道选择题，就是要卡住大量只会背"硬币找零用动态规划"结论的考生——你不需要会写 DP 方程，只需要能一眼看出代码里每一步局部最优选择累加，就是贪心。五级这里不是考你"会不会贪心"，而是考你"是否理解贪心与 DP 的本质区别"。