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