APP
動態(tài)規(guī)劃問題之貪婪算法實現(xiàn)硬幣最優(yōu)解
貪婪問題實現(xiàn)最少的硬幣找零問題：
start_time = time.time()
end_time = time.time()
print(‘Took %f second’ % (end_time - start_time))
是我們加入用來計算運算時間的
首先定義一個函數(shù)：rec(coinValueList,change) 其中coinValueList是我們的硬幣的面值，change是我們的需要找零的金額
[c for c in coinValueList if c<=change]：這里創(chuàng)建一個列表用來存儲這次找零可以用到的面值金額，然后進(jìn)行循環(huán)調(diào)用和遞歸運算。
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))
我們可以看出這種算法耗時非常多，需要進(jìn)行優(yōu)化：
加入一個可查詢的列表，就不用重復(fù)計算已經(jīng)算過的此面值最優(yōu)的找零方法，可以節(jié)約非常巨大的一部分時間。
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))
本文摘自 ：https://blog.51cto.com/u
