获得总金额的最小硬币数量

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 。