動態變化的決策算法，返回用於硬幣的實際列表

Question

我試圖調整從維基百科的代碼：

https://en.wikipedia.org/wiki/Change-making_problem#Implementation

要還輸出使用，不僅數量硬幣的列表使用的硬幣。也就是說，例如：

change_making([6, 8, 12], 52)輸出5這是正確的（12+12+12+8+8 = 52）。

問題是我想以這種格式得到輸出[12, 12, 12, 8, 8]而不是隻有5我不知道該怎麼做。

有問題的代碼：

def _get_change_making_matrix(set_of_coins, r): 
    m = [[0 for _ in range(r + 1)] for _ in range(len(set_of_coins) + 1)] 

    for i in range(r + 1): 
     m[0][i] = i 

    return m 


def change_making(coins, n): 
    """This function assumes that all coins are available infinitely. 

    n is the number that we need to obtain with the fewest number of coins. 

    coins is a list or tuple with the available denominations.""" 

    m = _get_change_making_matrix(coins, n) 

    for c in range(1, len(coins) + 1): 

     for r in range(1, n + 1): 

      # Just use the coin coins[c - 1]. 
      if coins[c - 1] == r: 
       m[c][r] = 1 

      # coins[c - 1] cannot be included. 
      # We use the previous solution for making r, 
      # excluding coins[c - 1]. 
      elif coins[c - 1] > r: 
       m[c][r] = m[c - 1][r] 

      # We can use coins[c - 1]. 
      # We need to decide which one of the following solutions is the best: 
      # 1. Using the previous solution for making r (without using coins[c - 1]). 
      # 2. Using the previous solution for making r - coins[c - 1] (without using coins[c - 1]) plus this 1 extra coin. 
      else: 
       m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]]) 

    return m[-1][-1] 

任何幫助/建議將不勝感激。

------------- ------------- EDIT

將該溶液（評論移除）：

def _change_making(coins, n): 
    m = [[0 for _ in range(n + 1)] for _ in range(len(coins) + 1)] 
    for i in range(n + 1): 
     m[0][i] = i 

    for c in range(1, len(coins) + 1): 
     for r in range(1, n + 1): 
      if coins[c - 1] == r: 
       m[c][r] = 1 
      elif coins[c - 1] > r: 
       m[c][r] = m[c - 1][r] 
      else: 
       m[c][r] = min(m[c - 1][r], 1 + m[c][r - coins[c - 1]]) 

    i = len(coins) 
    j = n 
    ret = {k: 0 for k in coins} 
    while j != 0: 
     if m[i][j - coins[i - 1]] == m[i][j] - 1: 
      ret[coins[i - 1]] += 1 
      j = j - coins[i - 1] 
     else: 
      i = i - 1 

    return ret 

要找到最接近 *解決方案：

def change_making(coins, n): 
    try: 
     return _generate_packing(coins, n) 
    except: 
     return generate_packing(coins, n + 1) 

例如change_making([2, 5], 8)

{2: 2, 5: 1} 

因爲9是最接近可能的解決方案。

• 由最靠近我的意思是一個解決方案，是能夠滿足，但高於原始請求。例如，如果我們需要返還8英鎊的變化，而我們沒有確切的變化，那麼我們將返回9英鎊，因爲我們確實有變化。

Answer 1

下面是步驟，你可以怎麼做 -

1）啓動與陣列的i=len(coins)和j=n即結束（或清單）m

2）現在我們知道的硬幣如果m[i][j]只使用比m[i][j-coins[i-1]]多一個硬幣，則選擇值coins(i-1)。 3）如果這沒有發生，我們檢查其他硬幣（列表中較低索引處的硬幣）是否具有相同的條件。

例 -

在開始我們有值52，我們已經解決了，它需要使用你的函數5枚硬幣。

我們使用的第一枚硬幣只有在價值40（即52 -12）時我們需要4枚硬幣，並且同樣適用於第二枚和第三枚12枚硬幣。

但我們無法使用第四個12硬幣作爲價值4（即16-12）無法使用1個硬幣實現。

下面是代碼片段做同樣的（你可以用它在你的函數的末尾，而不是return語句） -

i=len(coins) 
j = n 
while(j!=0): 
    if m[i][j-coins[i-1]] == m[i][j]-1: 
     print(coins[i-1]) 
     j=j-coins[i-1] 
    else: 
     i=i-1