当前位置 博文首页 > 是Dream呀的博客：动态规划问题之贪婪算法实现硬币最优解
贪婪问题实现最少的硬币找零问题：
start_time = time.time()
end_time = time.time()
print(‘Took %f second’ % (end_time - start_time))
是我们加入用来计算运算时间的
首先定义一个函数：rec(coinValueList,change) 其中coinValueList是我们的硬币的面值，change是我们的需要找零的金额
[c for c in coinValueList if c<=change]：这里创建一个列表用来存储这次找零可以用到的面值金额，然后进行循环调用和递归运算。
import time
start_time = time.time()
def rec(coinValueList,change):
minCoins=change
if change in coinValueList:
return 1
else:
for i in [c for c in coinValueList if c<=change]:
numCoins=1+rec(coinValueList,change-i)
if numCoins<minCoins:
minCoins=numCoins
return minCoins
print(rec([1,5,10,25],63))
end_time = time.time()
print('Took %f second' % (end_time - start_time))
我们可以看出这种算法耗时非常多，需要进行优化：
加入一个可查询的列表，就不用重复计算已经算过的此面值最优的找零方法，可以节约非常巨大的一部分时间。
import time
start_time = time.time()
def rec(coinValueList,change,list):
minCoins=change
if change in coinValueList:
list[change]=1
return 1
elif list[change]>0:
return list[change]
else:
for i in [c for c in coinValueList if c<=change]:
numCoins=1+rec(coinValueList,change-i,list)
if numCoins<minCoins:
minCoins=numCoins
list[change]=minCoins
return minCoins
print(rec([1,5,10,25],63,[0]*64))
end_time = time.time()
print('Took %f second' % (end_time - start_time))
