贪心算法找零钱问题

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