给定金额和面额的最小硬币数量

Question

给定一组面额和所需的总和我必须找到最低数量的硬币使该总和以及硬币的数量为每个面额

请帮忙！！

Answer 1

代码中有3个错别字：

第一：

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

这应该是：

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

第二：同样在前面的代码中，min的第二部分缺少1，因此正确的代码为

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

第三：

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] 
      // <---- HERE
    end if
end while

在这里，我们应该将min重新分配到新单元格，因此正确的代码将是：

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]
        min = dp[I][j]    
    end if
end while

非常感谢的解决方案。

Answer 2

确定该金额所需最小硬币数量的伪代码为：

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                 //if the denomination is greater than total
            dp[i][j] := dp[i-1][j] 
        else                           //if the denomination is less than or equal to total
            dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
        end if
    end for
end for
Return dp[n-1][total]

并找出所需的面额：

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          //if the value came from the top we didn't choose current coin
        i := i - 1
    else
        Print(coins[i])
        j := j - coins[i]
    end if
end while

如果您想打印每个面额的数字，在打印硬币[i]之后，您需要打印dp[j]和dp[j-硬币[i]的差值。代码的其余部分将是相同的。

此解决方案的完整说明以前可以在SO文档中找到，但现在已移至此处。

给定不同面额的硬币和总数，如果我们使用最少数量的硬币，我们需要组合多少硬币才能得到总数？假设我们有coins={1,5,6,8}和total=11，我们可以使用{5,6}的两个硬币得到总数。这确实是获得11枚硬币所需的最低数量。我们还假设硬币的供应是无限的。我们将使用动态规划来解决这个问题。

我们将使用2D数组dp[n][总计1]，其中n是我们拥有的不同面值硬币的数量。对于我们的例子，我们需要dp[4][12]。这里dp[i][j]表示如果我们有硬币从硬币[0]到硬币[i]，得到j所需的最小硬币数。例如dp[1][2]将存储如果我们有硬币[0]和硬币[1]，我们可以用来制作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]

这个条件将是真实的，直到我们的总数是5在dp[1][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-硬币[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*总计），其中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

对于我们的例子，方向将是：

数值将为6,5。