獲得總金額的最小硬幣數量

Created: November-22, 2018

鑑於不同面額和總額的硬幣，如果我們使用最小數量的硬幣，我們需要合併多少硬幣才能獲得總額？假設我們有 coins = {1, 5, 6, 8} 和 total = 11，我們可以使用 2 個硬幣來獲得總數，這是 {5, 6}。這確實是獲得 11 所需的最小硬幣數量。我們還假設有無限量的硬幣供應。我們將使用動態程式設計來解決這個問題。

我們將使用 2D 陣列 dp [n] [total + 1] ，其中 n 是我們擁有的不同硬幣面額的數量。對於我們的例子，我們需要 dp [4] [12] 。這裡 dp [i] [j] 將表示如果我們從硬幣[0] 到硬幣[i] 有硬幣，則獲得 j 所需的最小硬幣數量。例如，如果我們有硬幣[0] 和硬幣[1] ， dp [1] [2] 將儲存，我們可以用來製作 2 的最小硬幣數量是多少。讓我們開始： **** **** **** **** **** ****

首先，對於第 0 列，可以通過不取任何硬幣來使 0 。因此第 0 列的所有值都將為 0 。對於 dp [0] [1] ，我們問自己，如果我們只有 1 個面額的硬幣，那就是硬幣[0] = 1 ，獲得 1 所需的最小硬幣數是多少？答案是 1 。對於 dp [0] [2] ，如果我們只有 1 ，那麼獲得 2 所需的最小硬幣數是多少。答案是 2 。同樣 dp [0] [3] = 3 ， dp [0] [4] = 4 ，依此類推。這裡要提到的一件事是，如果我們沒有一個面額硬幣 1 ，可能會出現一些僅使用 1 枚硬幣無法實現總額的情況。為簡單起見，我們在示例中取 1 。在第一次迭代後，我們的 dp 陣列將如下所示：

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

繼續，對於 dp [1] [1] ，我們問自己是否有硬幣[0] = 1 而硬幣[1] = 5 ，獲得 1 所需的最小硬幣數量是多少？由於硬幣[1] 大於我們當前的總數，因此不會影響我們的計算。我們需要排除硬幣[5] 並僅使用硬幣[0] 獲得 1 。該值儲存在 dp [0] [1]中。所以我們從頂部獲取價值。我們的第一個公式是： **** ****

if coins[i] > j
    dp[i][j] := dp[i-1][j]

在 dp [1] [5]中我們的總數為 5 之前，這種情況才會成立，對於這種情況，我們可以用兩種方式製作 5 ： **** ****

我們取 5 個硬幣[0] 面額，它儲存在 dp [0] [5] （從頂部）。
我們採用 1 個面額的硬幣[1] 和（ 5 - 5 ）= 0 面額的硬幣[0] 。

我們將選擇這兩者中的最小值。所以 dp [1] [5] = min（ dp [0] [5] ， 1 + dp [1] [0] ）= 1 。為什麼我們提到 0 個硬幣的**面額[0]，**這將在我們的下一個位置顯而易見。

對於 dp [1] [6] ，我們可以用兩種方式製作 6 ：

我們採用 6 種面額的硬幣[0] ，儲存在頂部。
我們可以取 1 個面額為 5 ，我們需要 6 - 5 = 1 來得到總數。使用面額 1 和 5 的硬幣獲得 1 的最小方式儲存在 dp [1] [1]中，其可以寫為 dp [i] [j-coins [i]] ，其中 i = 1 。這就是為什麼我們以這種方式寫出之前的價值。 **** **** **** **** **** ****

我們將採用這兩種方式中的最小值。所以我們的第二個公式是：

if coins[i] >= j
    dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])

使用這兩個公式我們可以填滿整個表格。我們的最終結果將是：

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 1 | 2 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

我們的要求結果將儲存在 dp [3] [11] 。程式將是：

Procedure coinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 0
end for
for i from 1 to (total + 1)
    dp[0][i] := i
end for
for i from 1 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j] 
        else
            dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
        end if
    end for
end for
Return dp[n-1][total]

該演算法的執行時複雜度為：O（n * total）其中 n 是硬幣的面額數。

要列印所需的硬幣，我們需要檢查：

如果值來自頂部，則不包括當前硬幣。
如果值來自左側，則包括當前硬幣。

演算法將是：

Procedure printChange(coins, dp, total):
i := coins.length - 1
j := total
min := dp[i][j]
while j is not equal to 0
    if dp[i-1][j] is equal to min
        i := i - 1
    else
        Print(coins[i])
        j := j - coins[i]
    end if
end while

對於我們的例子，方向將是：

https://i.stack.imgur.com/hFZil.jpg

該值將是 6 ， 5 。