動態規劃：硬幣的最小號碼進行變更爲65美分

Question

我試圖使用動態編程來解決問題和問題產生如下：

鑑於硬幣（便士，鎳，角錢的無限量供應，二分之一，四分之一）與 值（1,5,10,20,25），請找到最小數量的硬幣進行65美分的更改。 使用哪些硬幣（以及每個硬幣的數量）？舉例說明使用動態編程算法所需的表格以及如何獲得使用的硬幣。

注意：我不希望任何人爲我說明整個表格，但是我對如何填寫表格解決此問題感到困惑。

我知道我的表看起來有點像這樣：

5 10 15 20 25 30 35 40 45 50 55 60 65 
1 

5 

10 

20 

25 

（我省略了1分的，因爲我知道這是不是最好的解決方案） 我最初的想法是，該表將填寫有點像這樣：

5 10 15 20 25 30 35 40 45 50 55 60 65 
1 

5 1 2 4 5 5 6 7 8 9 10 11 12 13 

10 0 1 

20 

25 

當我不得不走得更遠時，我陷在這裏。我不認爲我完全理解動態編程如何對這個問題起作用。我一直在閱讀我的書，並在網上閱讀，但我仍然有點困惑。

編輯：

多虧了一個答案這是我摸索出瞭解決方案：

5  10 15 20 25 30 35 40 45 50 55 60 65 
1 

5 1   1     1        1   

10   1 1      1        1  

20     1      2  1      2 

25       1  1 1   1  2  2  2  1 

Answer 1

你做錯了。這些列表示您必須返回的總體變化，並且行單元格表示使用的某些硬幣（一分錢，鎳，一角，二分錢，四分之一）的數量。

該算法的重點是返回最小數量的硬幣。例如，如果更改爲25，則應該返回一個季度，而不是25個便士。你可以看到我在下表中使用了25美分的四分之一。

在你的例子中，對於15變化的列，你使用的是4 x 5cents，這是次優的，因爲你可以使用一個10美分的硬幣和一個5的硬幣返回總共15個。在20美分列使用5 x 5美分的變化，這是不正確的，也不是最優的，因爲你可以用一個20美分的硬幣返還20美分。

這是一張表格，填寫前5列。您可以填寫其他內容：

5 10 15 20 25 30 35 40 45 50 55 60 65 
1 

5 1  1  

10  1 1 

20    1 

25     1 
-------------------------------------------------------- 
T 1 1 2 1 1 

我在底部添加了一個T行來計算您用作更改的硬幣總數。你的目標是獲得最低分數。這一行中每列的可能數字。

Answer 2

仍然使用動態規劃，我會將問題建模爲構造一個圖，其中節點爲金額（節點N爲N美分），並且其中有5種類型的有向邊{1，5，10 ，20,25}，對應於硬幣類型。

保持尚未找到最佳解決方案的節點的運行前沿。每次迭代時，邊界上的最小節點必須是最優的，因此可以將其刪除，並將最多5個新節點添加到邊界上。

這裏是的Python算法：

def change(coins, target): 
    nodes = {0: (0, None)} 
    frontier = set([0]) 
    while True: 
     n = min(frontier) 
     frontier.remove(n) 
     if n == target: 
      break 
     elif n > target: 
      return None # Infeasible! 
     count = nodes[n][0] 
     for coin in coins: 
      m = n + coin 
      frontier.add(m) 
      if not m in nodes or nodes[m][0] > count + 1: 
       nodes[m] = (count + 1, n) 
    m = target 
    sol = {} 
    while True: 
     n = nodes[m][1] 
     if n is None: 
      break 
     coin = m - n 
     sol[coin] = sol.get(coin, 0) + 1 
     m = n 
    return sol 

print change([1, 5, 10, 20, 25], 65) 

輸出是{25: 1, 20: 2}。