5.贪心算法

贪心算法

用局部最优解来推导全局最优解是对遍历空间的一种优化

难点：当前最优解未必是全局最优解

问题描述：

现在市面上有6中不同面值的硬币，各硬币的面值分别为5分、1角、2角、5角、1元、2元。

假定商店里各面值的硬币数量无限，小明想买一只标价为0.55元的棒棒糖。

代码实现：

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

总结：

通过从大到小的策略，不断的求取面额的最大数量（money[InvalidCharacterError: "MAX*N）<" did not match the Name production]