场景描述
在超市结账时，假设只有1分、5分、1角、3角、5角、1元的硬币，如果需要找零钱，给定需要找的零钱数目，使收银员找给顾客的硬币数量最少，运行程序如图：
知识补充
贪心算法是指在当前问题求解中，总是做出当前的最好选择，也就是局部最优解！使用贪心策略必须保证无后效性，也就是某个状态以后的过程不会影响到状态之前，同时局部最优策略可以产生全局最优解。
贪心算法一般的解决步骤是：
1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部最优解；
4.把子问题的局部最优解合成原来问题的一个解。
定义函数功能
初始化收银员拥有零钱数
通过input得到每种零钱数量，定义收银员拥有的总零钱数，防止无法进行找零，同时确定各面值硬币的数量。
"""
通过输入获取总零钱
"""
def new_coin():
print("=====收银员总零钱统计=====")
coin = [0.01, 0.05, 0.1, 0.5, 1.0]
coin_num = []
sum = 0
for index, i in enumerate(coin):
num = int(input('收银员{}面值硬币有几个？'.format(i)))
coin_num.append(num)
sum += i * num
print("收银员总零钱数:{0}".format(sum))
return sum, coin, coin_num编写找零
从最大硬币面值开始，计算这一类面值可以找多少金额，每一类面值硬币的找零数量就是一个子问题，同时汇总以达到总硬币数最小的目标。
"""
计算找零
"""
def change(sum, coin, coin_num):
print('==========找零==========')
s = float(input("请输入要找零金额:"))
# 找零比收银员总零钱数大
if s > sum:
print("收银员零钱不够！")
else:
# 贪心算法要总硬币数最少，从最大面值开始找零
i = len(coin) - 1
while i >= 0:
if s >= coin[i]:
n = int(s / coin[i])
if n > coin_num[i]:
n = coin_num[i]
#贪心算法 动态改变找零总值
s -= n * coin[i]
print("用了{0}面值的硬币{1}个".format(coin[i], n))
i -= 1
print("找零结束！")完整代码实现
"""
通过输入获取总零钱
"""
def new_coin():
print("=====收银员总零钱统计=====")
coin = [0.01, 0.05, 0.1, 0.5, 1.0]
coin_num = []
sum = 0
for index, i in enumerate(coin):
num = int(input('收银员{}面值硬币有几个？'.format(i)))
coin_num.append(num)
sum += i * num
print("收银员总零钱数:{0}".format(sum))
return sum, coin, coin_num
""" 计算找零 """
def change(sum, coin, coin_num):
print('==========找零==========')
s = float(input("请输入要找零金额:"))
# 找零比收银员总零钱数大
if s > sum:
print("收银员零钱不够！")
else:
# 贪心算法要总硬币数最少，从最大面值开始找零
i = len(coin) - 1
while i >= 0:
if s >= coin[i]:
n = int(s / coin[i])
if n > coin_num[i]:
n = coin_num[i]
#贪心算法 动态改变找零总值
s -= n * coin[i]
print("用了{0}面值的硬币{1}个".format(coin[i], n))
i -= 1
print("找零结束！")
if __name__ == '__main__':
print("============收银员找零================")
sum, coin, coin_num = new_coin()
change(sum, coin, coin_num)
