文章目錄
- 一、分治政策與遞歸算法
-
- 1. 分治政策的概念
- 2. 分治政策與遞歸算法的關系
- 二、優化問題和貪心政策
-
- 1. 優化問題
- 2. 貪心政策
- 3. 貪心政策失效
- 三、找零問題的遞歸解法
-
- 改進遞歸算法解決方案
- 四、找零問題的動态規劃解法
-
- 1. 動态規劃解法
- 2. 動态規劃中最主要的思想
- 3. 找零兌換：動态規劃算法擴充
一、分治政策與遞歸算法
1. 分治政策的概念
分治政策是解決問題的典型政策：分而治之。将問題分為若幹更小規模的部分通過解決每一個小規模部分問題，并将結果彙總得到原問題的解。
2. 分治政策與遞歸算法的關系
-
遞歸算法展現了分治政策：
問題解決依賴于若幹縮小了規模的問題，彙總得到原問題的解。
-
應用相當廣泛：
排序、查找、周遊、求值等等，都用到了分治政策，且大多都是由遞歸算法實作的。
二、優化問題和貪心政策
1. 優化問題
計算機科學中許多算法都是為了找到某些問題的最優解。我們很難計算出這些問題的最優解，隻能不斷的向這個最優解靠近。
一個經典案例是兌換最少個數的硬币問題：
假設你為一家自動售貨機廠家程式設計式，自動售貨機要每次找給顧客最少數量硬币；
假設某次顧客投進1美元的紙币，買了37美分的東西，要找63美分，那麼最少數量就是：兩個25分硬币、一個10分硬币和三個1分硬币，一共6個硬币。
2. 貪心政策
解決上面的找零問題，我們的第一反應通常是使用最直覺的“貪心政策”。使用如下方法解決：
從面值最大的硬币開始，盡量找大面值的硬币，等剩餘要找的錢不足一個該面值的硬币，再換面值小一點的找零，以此類推。
3. 貪心政策失效
還是找零問題，但這次硬币的面值除了上面的三種外，多了一種21美分的面值。
此時，如果還按照貪心政策，則需要 25 × 2 + 10 × 1 + 1 × 3 25 \times 2 + 10 \times 1 + 1 \times 3 25×2+10×1+1×3，總共六個硬币。因為，找完兩個25美分後，剩下的13美分不足一個21美分硬币。是以，沒有使用21美分硬币。
但如果一上來就使用21美分硬币，那麼則隻需要三個21美分硬币。
貪心政策最終失效了，沒有給出最優解。
三、找零問題的遞歸解法
接下來的遞歸算法則彌補了貪心算法的不足，它可以百分之百的給出最優解。
-
首先是确定基本結束條件，兌換硬币這個問題最簡單直接的情況就是，需要兌換的找零，其面值正好等于某種硬币。
如找零25分，答案就是1個硬币！
- 其次是減小問題的規模，我們要對每種硬币嘗試1次，例如美元硬币體系：
-
找零減去1分後，求兌換硬币最少數量（遞歸調用
自身）；
-
找零減去5分後，求兌換硬币最少數量（遞歸調用
自身）；
-
找零減去10分後，求兌換硬币最少數量（遞歸調用
自身）；
- 找零減去25分(quarter)後，求兌換硬币最少數量（遞歸調用自身）；
-
python代碼實作：
def recMC(coinValueList, change):
"""
使用遞歸算法解決找零問題
:param coinValueList: 貨币體系，是一個清單，儲存硬币的各種面值
:param change: 找零的金額
:returns: 找零花費的最少硬币數量
"""
# 初始化最少硬币數
minCoins = change
# 遞歸出口：如果要找的金額恰好是某一個面值的硬币就傳回1
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))
這段代碼有點難懂，但其實它的實質是排列組合出所有的找零可能，是以，它的效率極其的低！
我在電腦上運作上述測試用例，花費了近20秒。然後加了一種面額，并提高找零金額到93，等了3分鐘還沒出結果，就放棄了😕
以找零26分錢為例，畫出部分調用過程（377次遞歸的一小部分）：
從圖中可以發現，遞歸算法的重複計算太多，比如找零15分出現了3次，而這僅僅是一小部分。
是以，對這個遞歸解法進行改進的關鍵就在于消除重複計算。
改進遞歸算法解決方案
我們可以用一個表将計算過的中間結果儲存起來，在計算之前查表看看是否已經計算過。
在遞歸調用之前，先查找表中是否已有部分找零的最優解。如果有，直接傳回最優解而不進行遞歸調用；如果沒有，才進行遞歸調用。
def recDC(coinValueList,change,knownResults):
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
return minCoins
print(recDC([1,5,10,25],63,[0]*64))
對于63分錢的找零問題，改進後的算法僅僅需要211次遞歸調用，是改進之前的三十萬分之一，瞬間傳回！
四、找零問題的動态規劃解法
上面改進後的算法，将中間結果記錄了下來，可以很好的解決找零兌換問題。但這種方法還不能稱為動态規劃，而是叫做“memoization（記憶化/函數值緩存）”。
1. 動态規劃解法
依舊是以找零問題為例：動态規劃算法從最簡單的“1分錢找零”的最優解開始，記錄下最優解，逐漸遞加上去（2分錢的最優解，3分錢的……），直到我們需要的找零錢數。
計算11分錢的兌換法，我們做如下幾步，從1分錢兌換開始，逐漸建立一個兌換表（橫向代表找零金額，縱向為需要的最少硬币數）：
- 首先減去1分硬币，剩下10分錢查表最優解是1
- 然後減去5分硬币，剩下6分錢查表最優解是2
- 最後減去10分硬币，剩下1分錢查表最優解是1
通過上述最小值得到最優解：2個硬币
問題的最優解包含了更小規模子問題的最優解，這是一個最優化問題能夠用動态規劃政策解決的必要條件。在找零問題中，這句話的意思就是找5分錢的最優解，我們必須擁有4分錢的最優解。
python代碼實作：
def dpMakeChange(coinValueList,change,minCoins): # minCoins用來存儲上面的那張表，大小為找零金額加一
# 從1分錢開始到change，因為range是左閉右開區間，是以加1
for cents in range(change+1):
# 初始化硬币數量，放入最大值
coinCount = cents
# 從cents中減去一種面值的金額
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents-j] + 1 < coinCount:
coinCount = minCoins[cents-j]+1
# 得到目前的最優解
minCoins[cents] = coinCount
# 傳回整體的最優解
return minCoins[change]
def dpMakeChange(coinValueList, change, minCoins):
# 從1分錢開始到change，因為range是左閉右開區間，是以加1
for cents in range(change + 1):
# 初始化硬币數量，放入最大值
coinCount = cents
#
for j in [c for c in coinValueList if c <= cents]:
# 從cents中減去所選面值的金額，剩餘金額的最優解查表擷取
if minCoins[cents - j] + 1 < coinCount:
coinCount = minCoins[cents - j] + 1
# 得到目前的最優解
minCoins[cents] = coinCount
# 傳回整體的最優解
return minCoins[change]
print(dpMakeChange([1, 5, 10, 21, 25], 63, [0]*64))
# 輸出：3
注意：這不是一個遞歸算法！
2. 動态規劃中最主要的思想
從最簡單情況開始到達所需找零的循環，其每一步都依靠以前的最優解來得到本步驟的最優解，直到得到答案。
3. 找零兌換：動态規劃算法擴充
前面的算法已經得到了最少硬币的數量，但沒有傳回硬币如何組合。我們現在想要具體的硬币組合，就需要對算法進行拓展。
擴充算法的思路很簡單，隻需要在生成最優解清單同時跟蹤記錄所選擇的那個硬币币值即可。
而在得到最後的解後，查詢一下對應金額記錄的步驟，然後減去選擇的硬币面額，再到記錄中查詢那一次所使用的面額……。如此反複回溯到表格之前的部分找零，就能逐漸得到每一步所選擇的硬币币值。
python代碼實作：
def dpMakeChange(coinValueList, change, minCoins, coinsUsed):
for cents in range(change + 1):
coinCount = cents
# 初始化新加入硬币的面額
newCoin = 1
for j in [c for c in coinValueList if c <= cents]:
if minCoins[cents - j] + 1 < coinCount:
coinCount = minCoins[cents - j] + 1
# 對應最小數量，所減的硬币面額
newCoin = j
minCoins[cents] = coinCount
# 記錄本步驟新加入的一個硬币的面額
coinsUsed[cents] = newCoin
return minCoins[change]
def printCoins(coinsUsed, change):
coin = change
while coin > 0:
# 到面額記錄中查詢記錄
thisCoin = coinsUsed[coin]
print(thisCoin)
# 減去面額後再次查詢
coin = coin - thisCoin
def main():
amnt = 63
clist = [1, 5, 10, 21, 25]
coinsUsed = [0] * (amnt + 1)
coinCount = [0] * (amnt + 1)
print("找零", amnt, "分錢需要：")
print(dpMakeChange(clist, amnt, coinCount, coinsUsed), "個硬币")
print("它們是：")
printCoins(coinsUsed, amnt)
print("面額記錄如下：")
print(coinsUsed)
main()
"""
輸出：
找零63分錢需要：
3 個硬币
它們是：
21
21
21
面額如下：
[1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 1, 1, 1, 1, 5, 1, 1, 1, 1, 10, 21, 1, 1, 1, 25, 1, 1, 1, 1, 5, 10, 1, 1, 1, 10, 1, 1, 1, 1, 5, 10, 21, 1, 1, 10, 21, 1, 1, 1, 25, 1, 10, 1, 1, 5, 10, 1, 1, 1, 10, 1, 10, 21]
"""
注意看面額21的位置：恰好就是63，63-21，63-21-21，這三個位置。