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

鉴于不同面额和总额的硬币,如果我们使用最小数量的硬币,我们需要合并多少硬币才能获得总额?假设我们有 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] = 3dp [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 来得到总数。使用面额 15 的硬币获得 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

该值将是 65