钱币找零.
本节学习解决钱币找零问题.这是一个非常经典的使用贪心算法解决的问题,即如何使用最少的钱币完成找零.
问题描述:假设1元,2元,5元,10元,20元,50元,100元的纸币的数量由count数组决定,现在要用这些钱来找零money元,至少要用多少张纸币?
思路解析:
试想如何能实现用最少纸币数完成找零,自然是优先选择面值较大的纸币.代码变量如下:
value变量:表示给定钱币的面值
count变量:表示给定的各个面值钱币的数量
money变量:表示找零金额
re变量:表示最终返回结果,即需要纸币张数,初始值为0
num变量:表示各种面值的钱币所需张数,作为一个中间变量存在
完整代码如下:
def change(value, count, money):
# 初始化返回的硬币数量为0
re = 0
# 从最大面额开始向下遍历，即从列表的末尾向前遍历
for i in range(len(value)-1, -1, -1):
# 计算当前面额的硬币最多可以使用多少枚
# num = min(剩余需要找零的金额 / 当前面额, 当前面额硬币的可用数量)
num = min(int(money / value[i]), count[i])
# 从剩余需要找零的金额中减去已经使用的硬币金额
money = money - num * value[i]
# 累加使用的硬币数量
re += num
# 如果遍历完所有面额后，剩余需要找零的金额仍然大于0
# 说明无法凑出指定的金额，返回-1
if money > 0:
return -1
# 如果能够凑出指定的金额，返回使用的硬币总数
return re