第13题硬币找零问题中要求找给客户最少的硬币。coins存储可用硬币规格，单位为角，假设规格都小于10角，且一定有1角规格。amount为要找零的金额，约定必须为1角的整数倍。输出为每种规格及其数量

第 189 题 / 共 251 题

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

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

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;
}

🎉

回答正确！

你真棒！

📝 题目解析

答案：A

知识点：贪心算法的应用，硬币找零问题的求解策略

解析：A正确，代码先排序再优先使用最大面额硬币，符合贪心算法思想；B错误，贪心算法并非对所有硬币组合都能得到最优解（如coins=[1,3,4], amount=6时，贪心会选4+1+1，最优为3+3）；C、D错误，代码未使用枚举或分治。