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

找零钱问题

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

#include #include 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 函数计算找零的硬币。最后，输出找零的结果。

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