自底向上的方法，以硬币的变化最小数量 [英] Bottom-up approach to minimum number of coins for change

问题描述

我构建一个自下而上的方法，以硬币找零问题。我不得不放弃，得到所要求的变化所需硬币的最小数目。它可以是可能的变化不能给予，因为给定的面额不能形成的值。

I am constructing a bottom-up approach to the coin change problem. I have to give the minimum number of coins needed to give the change requested. It may be possible that the change could not be given because the given denominations cannot form the value.

例如，它给定的面额为{4,8}，他们索要5那么它是不可能给我5.构建程序以下的变化，它适用于大多数情况下，除非它是不可能形成所要求的变化。例如，当面额只是{4}和I要求5，它返回其中之一是错误的。我能做些什么来解决这个问题？

For example, it the given denominations are {4, 8} and they ask for a change of 5 then it is impossible to give 5. I constructed the program below and it works well for most situations unless it is impossible to form the requested change. For example, when the denominations is just {4} and I request 5, it returns one which is false. What can I do to correct this problem?

下面P重新presents要求的变化， S分别存储在数组面额[]从索引0至S面额的数目 - 1. DP是二维阵列进行计算初始化为-1

Here P represents the change requested, S are the number of denominations stored in the array denominations[] from index 0 to S - 1. dp is a two dimensional array for calculation initialized to -1.

for (int i = 0; i <= P; ++i) {
    for (int j = 0; j < S; ++j) {
        int ans, x, y;

        // Min. no. of coins with current coin
        x = (i - denominations[j] >= 0) ? dp[i - denominations[j]][j] + 1: 0;

        // Min. no. of coins w/o current coin
        y = (j > 0) ? dp[i][j - 1] : 0;

        ans = min(x, y);
        if (ans == 0) ans = max(x, y);
        dp[i][j] = ans;
    }
}

感谢你的帮助。

推荐答案

该错误是，你没有正确处理时，它是被禁止的情况下的两个使用当前的硬币，和不使用它。这发生在你的榜样情况下，例如：当i = 1和j = 0，我们正在努力使总量1c的使用无论是什么，或只是一个4C钱币但我们不能用4C硬币做到这一点，并没有4C硬币，我们不能这样做，要么。

The bug is that you aren't correctly handling the case when it is forbidden both to use the current coin, and not to use it. This occurs in your example case, for instance: when i=1 and j=0, we are trying to make a total of 1c using either nothing or just a 4c coin; but we can't do this with a 4c coin, and we can't do it without a 4c coin either.

在这种情况下，x和y都将被分配为0，和行如果（ANS == 0）ANS =最大（X，Y）; ，这旨在捕获时的或者的的可能性被禁止的情况下，蜿蜒不正确分配0至答。外环将因此认为，它有可能使相应总和总计不硬币任何，并且愉快地加1，这一点，给予不正确的答案1为你的例子的后面的迭代

In such cases, both x and y will be assigned 0, and the line if (ans == 0) ans = max(x, y);, which is designed to catch the case when either of the possibilities are forbidden, winds up incorrectly assigning 0 to ans. Later iterations of the outer loop will consequently "think" that it is possible to make the corresponding sum for a total of no coins whatsoever, and blithely add 1 to this, giving the incorrect answer of 1 for your example.

最干净的修复，我认为，是选择大于0的不同的警戒值重新present这个动作是不可能的，不应被视为。既然你结合这两种可能的行动， MIN（），具有极高的价值，自然适合：

The cleanest fix, I think, is to choose a different sentinel value than 0 to represent "This action is impossible and should not be considered". Since you're combining the two possible actions with min(), an extremely high value fits naturally:

#define INF (INT_MAX-1)   // Or anything higher than the biggest sensible answer

for (int i = 0; i <= P; ++i) {
    for (int j = 0; j < S; ++j) {
        int ans, x, y;

        // Min. no. of coins with current coin
        x = (i - denominations[j] >= 0) ? min(INF, dp[i - denominations[j]][j] + 1) : INF;

        // Min. no. of coins w/o current coin
        y = (j > 0) ? dp[i][j - 1] : INF;

        ans = min(x, y);
        dp[i][j] = ans;
    }
}

请注意行 ANS = MIN（X，Y）; 现在给出正确的答案没有进一步的工作，包括它应该是这样的 INF ，因为x和y是 INF 。

Notice how the line ans = min(x, y); now gives the right answer without further work, including the case where it should be INF because both x and y are INF.

一个更微妙的一点是，当我们的读的一些 DP [A] [B] 在我们的计算中，该值允许为 INF ：这是一个合理的值，这说明 A 仙不能言用的类型＆lt硬币的任意组合; = B 。理想情况下，该值选择了 INF 将不得不在，添加或用任何正值乘以离开它INF属性 ，从那以后，我们就不会进行任何进一步的调整算法：我们在一个 INF 值会正常离开它 INF执行每一个操作。但是，整数运算不会按照这种方式，所以添加一些的值，可能是在 INF ，我们需要检查，我们还没有走过去无穷大，修复它如果是这样：这就是为什么 D [我 - 教派[J] [J] + 1 包装在分（INF，.. 。）通话。 （这也是为什么我定义的 INF 比 INT_MAX 一个都不能少 - 这样就不会发生溢出。 ）

A more subtle point is that when we read some dp[a][b] during our calculations, that value is allowed to be INF: this is a legitimate value, indicating that a cents can't be made with any combination of coins of type <= b. Ideally, the value chosen for INF would have the property that adding or multiplying it with any positive value leaves it at INF, since then we wouldn't have to make any further adjustments to this algorithm: every operation we perform on an INF value would correctly leave it at INF. But integer arithmetic doesn't work that way, so after adding something to a value that could be INF we need to check that we haven't "gone past infinity" and fix it up if so: that's why d[i - denominations[j]][j] + 1 is wrapped in a min(INF, ...) call. (This is also why I defined INF to be one less than INT_MAX -- so that overflow can't occur.)

这篇关于自底向上的方法，以硬币的变化最小数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！