c++贪心算法 找零钱

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

相关问题

贪心算法找零钱问题

假设有 $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;
}

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

好的，这是一个经典的贪心算法问题。我们假设有一些硬币，它们的面值为 1，5，10，20，50，100 元。现在需要找给顾客一定数量的零钱，问如何用最少的硬币数找给顾客？

我们可以使用贪心算法来解决这个问题。具体做法如下：

1. 首先将硬币按面值从大到小排序。

2. 从面值最大的硬币开始，不断地用当前面值的硬币去尽量多地找零，直到找完或者不能再找为止。然后再用下一个面值的硬币去找零，以此类推。

3. 直到找完所有需要找的零钱为止。

下面是 C++ 的代码实现：

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

vector<int> coins = {100, 50, 20, 10, 5, 1};  // 硬币面值

vector<int> change(int n) {
    vector<int> result;
    for (int i = 0; i < coins.size() && n > 0; i++) {
        while (n >= coins[i]) {
            result.push_back(coins[i]);
            n -= coins[i];
        }
    }
    return result;
}

int main() {
    int n = 123;
    vector<int> result = change(n);
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    return 0;
}

这里我们定义一个 `change` 函数，它接受一个正整数 `n`，表示需要找的零钱数，返回一个由硬币面值组成的向量 `result`，表示找零的方案。在函数中，我们按照硬币面值从大到小的顺序循环，每次用当前面值的硬币尽量多地找零，直到找完或者不能再找为止。最后返回找零方案即可。

注意，这个贪心算法的正确性是显然的，因为每次都使用当前面值的硬币尽量多地找零，所以能够保证找到最优解。