python 贪心算法硬币找钱问题

Question

设有6 种不同面值的硬币，各硬币的面值分别为5 分，1 角，2 角，5 毛，1 元，2元。现要用这些面值的硬币来购物。在购物中希望使用最少个数硬币。例如，1 次购物需要付款0.55 元，如果没有5 角的硬币，只好用2∗2角+1∗1角+1∗5分 共4 枚硬币来付款。

对于给定的各种面值的硬币个数和付款金额，计算使用硬币个数最少的交易方案。

输入格式:
输入数据有若干组，第一行给出一个整数n表示输入数据的组数。

以下n行每一行有6 个整数和1个有2 位小数的实数。分别表示可以使用的各种面值的硬币个数和付款金额。

输出格式:
输出每组数据的最少硬币个数。如果不可能完成交易，则输出“impossible”。

输入样例:
2
2 4 2 2 1 0 0.95
2 4 2 0 1 0 0.55
输出样例:
4
4

Answer 1

par = [0.05,0.1,0.2,0.5,1.0,2.0] #存储每种硬币，从小到大排列
sum = float(input("请输入需要找的零钱:")) 
#从面值最大的开始遍历
i = len(par) -1
while i >= 0:
    if sum >= par[i]:
        n = int(sum // par[i])
        change = n * par[i]
        sum = float("%.6f" %(sum - change))
        print("用了%d个%1.2f元硬币" % (n,par[i]))
    i -= 1

par是硬币种类,可以自行修改
有帮助请点击采纳,谢谢