找零錢的算法
1. 很慢的遞歸解決方案
# 遞歸版本
def recMC(coinValueList, change):
minCoins = change
if change in coinValueList:
return 1
else:
for i in [c for c in coinValueList if c < change]:
numCoins = 1 + recMC(coinValueList, change-i)
if numCoins < minCoins:
minCoins = numCoins
return minCoins
print(recMC([1,5,10,25], 63))
2. 添加了查詢表的找零算法
def recDC(coinValueList, change, knownResults):
start = time.time()
minCoins = change
if change in coinValueList:
knownResults[change] = 1
return 1
elif knownResults[change] > 0:
return knownResults[change]
else:
for i in [c for c in coinValueList if c < change]:
numCoins = 1 + recDC(coinValueList, change-i, knownResults)
if numCoins < minCoins:
minCoins = numCoins
knownResults[change] = minCoins
end = time.time()
length = end - start
print(length)
return minCoins
3.動態(tài)規(guī)劃版本的找零算法
# 動態(tài)規(guī)劃版本找零問題
def dpMakeChange(coinValueList, change, minCoins, coinUsed):
for cents in range(change+1):
coinCount = cents
new_coin = 1
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents-j] + 1 < coinCount:
coinCount = minCoins[cents-j] + 1
new_coin = j
minCoins[cents] = coinCount
coinUsed[cents] = new_coin
return minCoins[change]
def printCoins(coinsUsed, change):
coin = change
while coin > 0:
thisCoin = coinsUsed[coin]
print(thisCoin)
coin = coin - thisCoin
c1 = [1,5,10,21,25]
coinUsed = [0]*64
coinCount = [0]*64
cnt = dpMakeChange(c1, 63, coinCount, coinUsed)
print(cnt)
printCoins(coinUsed, 63)
printCoins(coinUsed, 52)
output:
3
21
21
21
10
21
21
