贪心算法之找零钱
贪心算法是一种在每一步选择中都采取在当前状态下最优的选择，从而希望能够得到全局最优解的算法策略。下面是一个经典的贪心算法实例：找零钱问题。
找零钱问题
假设你是一个收银员，需要找零给客户。你有以下面额的硬币：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;
}
逐行解释：
-
makeChange函数：这个函数接受一个整数amount作为参数，代表需要找零的金额。在函数内部，我们定义了一个硬币面额的向量coins，然后通过贪心算法，从面额最大的硬币开始尽可能多地找零，直到找完为止。 -
main函数：在主函数中，我们设定了需要找零的金额为63，然后调用makeChange函数计算找零的硬币。最后，输出找零的结果。
这个例子中，贪心算法的思路是每次选择面额最大的硬币，以尽可能减少硬币的数量。在这个问题中，贪心算法的选择是合理的，因为硬币的面额是整除关系，可以保证每次选择的硬币都是最优解。然而，并非所有问题都适合贪心算法，因为它不一定能得到全局最优解。