动态规划问题之贪婪算法实现硬币最优解

动态规划问题之贪婪算法实现硬币最优解

贪婪问题实现最少的硬币找零问题：

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))