找零钱问题贪心算法c++

找零钱问题可以用贪心算法来解决。贪心算法的核心思想是每次选择当前最优的解，直到达到全局最优。

假设有一张纸币面值数组 denominations 和一个要找的钱数 amount，现在要求用最少的纸币数来找零。

C++代码如下：

int coinChange(vector<int>& denominations, int amount) {
    sort(denominations.begin(), denominations.end()); // 将面值数组排序
    int count = 0;
    for (int i = denominations.size() - 1; i >= 0; i--) { // 从大到小遍历面值数组
        while (amount >= denominations[i]) { // 如果钱数大于等于当前面值
            amount -= denominations[i]; // 找一张当前面值的纸币
            count++; // 纸币数加 1
        }
    }
    return amount == 0 ? count : -1; // 如果钱数为 0，返回纸币数，否则返回 -1
}

首先将面值数组排序，然后从大到小遍历面值数组。每次循环中，如果钱数大于等于当前面值，就找一张当前面值的纸币，并将钱数减去当前面值。如果钱数小于当前面值，则继续遍历下一个面值。

最后如果钱数为 0，返回纸币数，否则返回 -1。

相关问题

c++贪心算法 找零钱

贪心算法是一种在求解问题时，每一步都选择当前状态下最优的解决方案，从而希望达到全局最优解的策略。在找零钱问题中，贪心算法可以应用于找零的过程。根据代码中的实现，该算法首先会从面值最高的纸币开始找零，然后逐渐使用面值较小的纸币直到完成找零或者无法找零为止。这种做法确保了每一次找零都是尽可能用最少的纸币数量。

贪心算法零钱找回问题c++代码

以下是贪心算法解决零钱找回问题的C++代码：

#include <iostream>
#include <vector>
using namespace std;

void change(vector<int>& coins, int amount) {
    sort(coins.begin(), coins.end()); // 从小到大排序
    int n = coins.size();
    int cnt = 0;
    for (int i = n - 1; i >= 0; i--) { // 从大到小遍历硬币
        while (amount >= coins[i]) { // 如果当前硬币可以用来找钱
            amount -= coins[i]; // 找钱
            cnt++; // 计数器加一
        }
    }
    if (amount == 0) {
        cout << cnt << endl; // 输出最少硬币数
    } else {
        cout << "无法找零" << endl;
    }
}

int main() {
    vector<int> coins{1, 2, 5, 10, 20, 50};
    int amount = 68;
    change(coins, amount);
    return 0;
}

其中，`coins` 为硬币面值数组，`amount` 为需要找零的金额。`change` 函数中，我们先将硬币面值从小到大排序，然后从大到小遍历硬币，每次找到一个硬币可以用来找钱，就计数器加一，直到找完所有的零钱或者无法找零。最后，如果找完所有的零钱，就输出最少硬币数，否则输出 "无法找零"。