c++ - 自下而上的方法来找零硬币的最小数量

Question

我正在构建一个自下而上的方法来解决硬币找零问题。我必须提供所需找零所需的最少硬币数。可能因为给定的面额无法形成值(value)而无法找零。

例如，给定的面额是 {4, 8} 并且他们要求找零 5 那么不可能给 5。我构建了下面的程序，它适用于大多数情况，除非无法形成请求的更改。例如，当面额仅为 {4} 而我请求 5 时，它返回一个错误。我该怎么做才能解决这个问题？

这里的P代表请求的变更，S是面额数组denominations[]中存储的面额数，从索引0到S-1。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 小一的原因——这样就不会发生溢出。)