Bottom-up approach to minimum number of coins for change

Question

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.

Answer 1

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.

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.

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

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.

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.)