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

好的，零钱找零问题可以使用贪心算法来解决。具体思路是，尽可能多地使用面值较大的钞票或硬币。以下是使用 C++ 实现的代码：

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

vector<int> changeCoins(int money, vector<int>& coins) {
    vector<int> ans;
    int n = coins.size();
    for (int i = n - 1; i >= 0; i--) {
        while (money >= coins[i]) {
            money -= coins[i];
            ans.push_back(coins[i]);
        }
    }
    return ans;
}

int main() {
    int money = 27;
    vector<int> coins = {1, 2, 5, 10, 20, 50};
    vector<int> ans = changeCoins(money, coins);
    for (int coin : ans) {
        cout << coin << " ";
    }
    cout << endl;
    return 0;
}

上述代码中，我们将钱币的面值按降序排列，然后从面值最大的钞票或硬币开始，尽可能多地使用它们，直到达到找零的金额为止。循环结束后，我们返回使用的钞票或硬币列表即可。