贪心算法之找零钱

贪心算法是一种在每一步选择中都采取在当前状态下最优的选择，从而希望能够得到全局最优解的算法策略。下面是一个经典的贪心算法实例：找零钱问题。

找零钱问题

假设你是一个收银员，需要找零给客户。你有以下面额的硬币：1元、5元、10元、25元。现在需要找零 n 元钱，问如何用最少的硬币数量找零？

#include <iostream>
#include <vector>

std::vector<int> makeChange(int amount) {
   
    std::vector<int> coins = {
   25, 10, 5, 1};  // 硬币面额
    std::vector<int> result;  // 存储找零的硬币

    for (int coin : coins) {
   
        while (amount >= coin) {
   
            result.push_back(coin);
            amount -= coin;
        }
    }

    return result;
}

int main() {
   
    int amount = 63;
    std::vector<int> change = makeChange(amount);

    std::cout << "Change for " << amount << " cents: ";
    for (int coin : change) {
   
        std::cout << coin << " ";
    }
    std::cout << std::endl;

    return 0;
}

逐行解释：

1. makeChange 函数：这个函数接受一个整数 amount 作为参数，代表需要找零的金额。在函数内部，我们定义了一个硬币面额的向量 coins，然后通过贪心算法，从面额最大的硬币开始尽可能多地找零，直到找完为止。

2. main 函数：在主函数中，我们设定了需要找零的金额为63，然后调用 makeChange 函数计算找零的硬币。最后，输出找零的结果。

这个例子中，贪心算法的思路是每次选择面额最大的硬币，以尽可能减少硬币的数量。在这个问题中，贪心算法的选择是合理的，因为硬币的面额是整除关系，可以保证每次选择的硬币都是最优解。然而，并非所有问题都适合贪心算法，因为它不一定能得到全局最优解。