自底向上的方法，以最小的硬币数量的变化

Question

我正在构造一个自底向上的方法来解决硬币更换问题。我必须给最低数量的硬币需要给要求的变化。有可能无法给出更改，因为给定的面额不能构成值。

例如，如果给定的面额是{4,8}，他们要求改变5，那么不可能给5。我构建了下面的程序，它在大多数情况下都能很好地工作，除非不可能形成所请求的更改。例如，当面值仅为{4}而我请求5时，它返回一个false。我能做些什么来纠正这个问题?

这里p代表请求的更改，S表示从索引0到S - 1存储在数组denominations[]中的名称个数。Dp是一个二维数组，用于初始化为-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;
    }
}

谢谢你的帮助。

Answer 1

错误是，当同时禁止使用当前硬币，和不使用它时，您没有正确处理这种情况。这发生在你的例子中，例如:当i=1和j=0时，我们试图用什么都不用或只用4c的硬币来制作总数1c;但是我们不能用4c的硬币来做这件事，没有4c的硬币我们也不能这样做。

在这种情况下，x和y都将被赋值为0，而if (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;
    }
}

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

更微妙的一点是，当我们在计算过程中读取一些dp[a][b]时，允许该值为INF :这是一个合法值，表明a分不能由任何类型的硬币<= b组合而成。理想情况下，为INF选择的值应该具有这样的属性，即将其与任何正值相加或相乘使其位于INF，因为这样我们就不必对该算法进行任何进一步的调整:我们对INF值执行的每个操作都将正确地使其位于INF。但是整数算术不能这样工作，所以在向可能是INF的值添加一些东西之后，我们需要检查我们没有"超过无穷大"并修复它，如果是这样:这就是为什么d[i - denominations[j]][j] + 1被包装在min(INF, ...)调用中。(这也是为什么我将INF定义为比INT_MAX小1的原因——这样就不会发生溢出。)