0

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.

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?

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;
    }
}

Thank you for your help.

4

1 回答 1

1

错误是当禁止使用当前硬币和不使用它时，您没有正确处理这种情况。这发生在您的示例案例中，例如：当 i=1 且 j=0 时，我们试图不使用任何东西或仅使用 4c 硬币来制作总共 1c；但是我们不能用 4c 硬币来做这件事，我们也不能没有 4c 硬币来做。

在这种情况下，x 和 y 都将被分配 0，而 lineif (ans == 0) ans = max(x, y);旨在捕捉任何一种可能性被禁止的情况，最终错误地将 0 分配给 ans。因此，外部循环的后续迭代将“认为”可以得出总共没有硬币的相应总和，并愉快地将其加 1，为您的示例给出 1 的错误答案。

我认为最干净的解决方法是选择一个不同于 0 的哨兵值来表示“这个动作是不可能的，不应该考虑”。由于您将两个可能的操作与 结合起来min()，因此自然适合极高的值：

#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;
    }
}

请注意，该行现在如何在没有进一步工作的情况下给出正确答案，包括因为 x 和 y 都ans = min(x, y);应该是的情况。INFINF

更微妙的一点是，当我们在计算过程中读取一些内容时，该值是允许的：这是一个合法值，表明不能用 <= 类型的硬币的任何组合来制造美分。理想情况下，为 选择的值将具有将其与任何正值相加或相乘的属性，因为这样我们就不必对这个算法进行任何进一步的调整：我们对一个值执行的每个操作都会正确地离开它在. 但是整数算术不是这样工作的，所以在将一些东西添加到可能是的值之后，我们需要检查我们是否没有“越过无穷大”并修复它：这就是为什么dp[a][b]INFabINFINFINFINFINFd[i - denominations[j]][j] + 1被包裹在一个min(INF, ...)电话中。（这也是我定义INF为小于一的原因INT_MAX——这样就不会发生溢出。）

于 2014-08-15T18:24:36.873 回答