贪心算法零钱找回问题

贪心算法零钱找回问题是指在给定一些硬币面值的情况下，找回指定数额的零钱所需的最小硬币数。使用贪心算法可以快速得到比较满意的解。具体实现方法是，每次选择面值最大的硬币，直到找回的零钱数额达到指定数额为止。以美元为例，假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币，要找回73美分的零钱，可以按照以下步骤进行：
- 选择面值为25美分的硬币，找回1个，剩余48美分；
- 选择面值为25美分的硬币，找回1个，剩余23美分；
- 选择面值为10美分的硬币，找回2个，剩余3美分；
- 选择面值为1美分的硬币，找回3个，剩余0美分。

因此，找回73美分的零钱所需的最小硬币数为7个。

相关问题

贪心算法零钱找回问题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` 函数中，我们先将硬币面值从小到大排序，然后从大到小遍历硬币，每次找到一个硬币可以用来找钱，就计数器加一，直到找完所有的零钱或者无法找零。最后，如果找完所有的零钱，就输出最少硬币数，否则输出 "无法找零"。

贪心算法找零钱问题

假设有 $n$ 种不同面值的硬币 $v_1, v_2, ..., v_n$，每种硬币的数量无限多。现在需要用这些硬币来支付 $m$ 元，最少需要多少个硬币？

贪心算法的思路是每次选择面值最大的硬币，直到无法再选择面值更大的硬币为止。具体实现需要按照硬币面值从大到小排序，然后依次选择硬币，直到总金额达到 $m$ 。以下是C++代码实现：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int minCoins(vector<int>& coins, int m) {
    sort(coins.begin(), coins.end(), greater<int>()); // 按硬币面值从大到小排序
    int count = 0;
    for (int i = 0; i < coins.size(); i++) {
        while (m >= coins[i]) { // 选择面值最大的硬币，直到无法再选择面值更大的硬币为止
            m -= coins[i];
            count++;
        }
    }
    return count;
}

int main() {
    vector<int> coins = {1, 5, 10, 20, 50, 100};
    int m = 128;
    cout << minCoins(coins, m) << endl; // 输出6
    return 0;
}