3.4.2 实践演练——解决“找零”问题

为了说明贪心算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解解决“找零”问题的方法。

1．问题描述

假设只有1分、2分、5分、1角、2角、5角、1元面值的硬币。在超市结账时，如果需要找零钱，收银员希望将最少的硬币数找给顾客。那么，给定需要找的零钱数目，如何求得最少的硬币数呢？

2．算法分析

在找零钱时可以有多种方案，例如补零钱0.5元时可有以下方案。

（1）1枚0.5元硬币。

（2）2枚0.2元硬币、1枚0.1元硬币。

（3）5枚0.1元硬币。

……

3．具体实现

编写实例文件ling.py，具体实现代码如下所示。

源码路径：daima\第3章\ling.py

def main():
    d = [0.01,0.02,0.05,0.1,0.2,0.5,1.0] # 存储每种硬币的面值
    d_num = [] # 存储每种硬币的数量
    s = 0
    # 拥有的零钱总和
    temp = input('请输入每种零钱的数量：')
    d_num0 = temp.split(" ")
    for i in range(0, len(d_num0)):
          d_num.append(int(d_num0[i]))
          s += d[i] * d_num[i] # 计算出收银员有多少钱
    sum = float(input("请输入需要找的零钱："))
    if sum > s:
         # 当输入的总金额比收银员的总金额多时，无法找零
         print("数据有错")
         return 0
    s = s - sum
    # 要想用的硬币数量最少，需要利用所有大面值的硬币，因此从数组的大面值的元素开始遍历
    i = 6
    while i >= 0:
         if sum >= d[i]:
              n = int(sum / d[i])
              if n >= d_num[i]:
                   n = d_num[i]  # 更新n
              sum -= n * d[i] # 贪心算法的关键步骤，令sum动态改变
              print("用了%d个%f枚硬币"%(n, d[i]))
         i -= 1
if __name__ == "__main__":
     main()

执行后，首先输入拥有的硬币个数，然后输入需要找零的金额，例如0.8元，按下Enter键后会输出找零方案：

请输入每种硬币的数量：12 11 11 11 11 11 11
请输入需要找的零钱：0.8
用了1枚0.500000元硬币
用了1枚0.200000元硬币
用了1枚0.100000元硬币
上一章目录下一章