找零钱问题贪心算法py

找零钱问题是指在给定一定面额的硬币和纸币的情况下，如何用最少的硬币和纸币来凑出一个指定的金额。贪心算法是一种常用的解决找零钱问题的方法，它的基本思想是每次选择面额最大的硬币或纸币来凑出指定金额，直到凑出的金额等于指定金额为止。使用Python语言编写的贪心算法可以直接运行，输入零钱金额后，输出找的零钱面值和数量。你可以参考以下代码实现：

def change_money(money, coins):
    coins.sort(reverse=True)
    res = []
    for coin in coins:
        while money >= coin:
            res.append(coin)
            money -= coin
    return res

if __name__ == '__main__':
    coins = [1, 5, 10, 50, 100]
    money = int(input("请输入零钱金额："))
    res = change_money(money, coins)
    print("找零面值和数量为：")
    for coin in set(res):
        print("{}元的硬币{}个".format(coin, res.count(coin)))

相关问题

找零钱问题贪心算法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`，表示找零的方案。在函数中，我们按照硬币面值从大到小的顺序循环，每次用当前面值的硬币尽量多地找零，直到找完或者不能再找为止。最后返回找零方案即可。

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

找零钱问题贪心算法c

贪心算法是一种常用的解决找零钱问题的方法。其核心思想是在每一步中选择最优解，从而得到全局最优解。在找零钱问题中，贪心算法采取的方式是找钱时，总是选取可供找钱的硬币的最大值。比如，需要找钱数为25时，找钱方式为20+5，而不是10+10+5。

下面是一个使用C语言实现的找零钱问题的贪心算法的例子：

/* 
 * m[ ]:存放可供找零的面值，降序排列 
 * k:可供找零的面值种类数 ,即m[ ]的长度 
 * n:需要找零数 
 */ 
#include <stdio.h> 

void getmoney(int m[],int k,int n){ 
    int i; 
    for( i=0;i<k;i++) { 
        while(n>=m[i]) { 
            printf("%d ",m[i]); 
            n=n-m[i]; 
        } 
    } 
    printf("\n"); 
} 

int main(){ 
    int n; 
    scanf("%d",&n); 
    int money[]={20,10,5,1}; 
    int k; 
    k=sizeof(money)/sizeof(int); 
    getmoney(money,k,n); 
}