找零钱问题贪心算法py
时间: 2023-11-19 15:56:14 浏览: 66
找零钱问题是指在给定一定面额的硬币和纸币的情况下,如何用最少的硬币和纸币来凑出一个指定的金额。贪心算法是一种常用的解决找零钱问题的方法,它的基本思想是每次选择面额最大的硬币或纸币来凑出指定金额,直到凑出的金额等于指定金额为止。使用Python语言编写的贪心算法可以直接运行,输入零钱金额后,输出找的零钱面值和数量。你可以参考以下代码实现:
```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
贪心算法是一种常用的解决找零钱问题的方法。其核心思想是在每一步中选择最优解,从而得到全局最优解。在找零钱问题中,贪心算法采取的方式是找钱时,总是选取可供找钱的硬币的最大值。比如,需要找钱数为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);
}
```
找零钱问题贪心算法c语言
找零钱问题是指在给定一定面额的硬币和需要找零的金额的情况下,如何使用最少的硬币找找零钱问题是指在给定一定面额的硬币和需要找零的金额的情况下,如何使用最少的硬币找零。贪心算法是一种常用的解决此类问题的方法,它的思路是每次选择当前可用的最大面额的硬币进行找零,直到找完为止。在C语言中,可以使用循环嵌套的方式来实现贪心算法解决找零钱问题。具体实现可以参考引用中的代码。同时,引用和引用中也提供了关于贪心算法的思路和实现方式的介绍。