Coin systems

A coin system is **canonical** if the greedy algorithm (take the largest coin that fits, repeat) gives the minimum number of coins for every amount. US coins 1, 5, 10, 25 are canonical, and so is any system in which each coin is a multiple of the next smaller one, such as powers of two. Systems like {1, 3, 4} and {1, 5, 10, 20, 25} are not.

Testing is finite: a non-canonical system with coins c1 < … < cn always has a counterexample amount smaller than c(n-1) + cn, so it is enough to compare greedy against the optimum for every amount below that bound. Doing so for {1, 5, 10, 20, 25} finds the smallest counterexample 40: greedy takes 25 + 10 + 5 for 3 coins, while 20 + 20 uses 2.

1// coins sorted ascending; returns the smallest amount where greedy is suboptimal, or -1 if canonical
2static int firstCounterexample(int[] coins) {
3    int n = coins.length;
4    if (n < 2) return -1;
5    int limit = coins[n - 1] + coins[n - 2];                 // a counterexample, if any, is below this
6    int[] best = new int[limit + 1];
7    Arrays.fill(best, Integer.MAX_VALUE);
8    best[0] = 0;
9    for (int a = 1; a <= limit; a++) {
10        for (int c : coins) if (c <= a && best[a - c] != Integer.MAX_VALUE) best[a] = Math.min(best[a], best[a - c] + 1);
11        int left = a, used = 0;
12        for (int i = n - 1; i >= 0; i--) { used += left / coins[i]; left %= coins[i]; }
13        if (left == 0 && used > best[a]) return a;           // greedy used more coins than the optimum
14    }
15    return -1;
16}

1static int greedyCoins(int[] coins, int amount) {         // coins sorted in descending order; -1 if stuck
2    int count = 0;
3    for (int c : coins) {
4        count += amount / c;                                // as many of the biggest coin as fit
5        amount %= c;
6    }
7    return amount == 0 ? count : -1;
8}

The greedy algorithm: sort coins descending, and for each coin take as many as fit, then move on. For amount 63 with US coins that is two 25s, one 10 and three 1s: 6 coins, which the “Canonical system (US coins)” preset confirms equals the optimum. “Powers of two” makes 13 with 8 + 4 + 1.

The loop divides rather than subtracts one coin at a time, so it costs O(number of coin types). The function reports -1 when it ends with amount left over, which can only happen if the smallest coin is larger than 1 (the “Greedy gets stuck” preset).

1// coins sorted descending; returns the number of coins used, or -1 if the amount cannot be formed greedily
2static int greedyCoins(int[] coinsDescending, int amount) {
3    int used = 0;
4    for (int c : coinsDescending) {
5        used += amount / c;
6        amount %= c;
7    }
8    return amount == 0 ? used : -1;
9}

1static int greedyCoins(int[] coins, int amount) {         // coins sorted in descending order; -1 if stuck
2    int count = 0;
3    for (int c : coins) {
4        count += amount / c;                                // as many of the biggest coin as fit
5        amount %= c;
6    }
7    return amount == 0 ? count : -1;
8}

Greedy can fail in two ways. It can be **suboptimal**: it forms the amount but uses too many coins ({1, 3, 4} and amount 6). It can also **get stuck**: it reaches a state with an amount that no remaining coin fits, although a different combination exists. The “Greedy gets stuck” preset uses coins {5, 4} and amount 8: greedy takes 5 and is left with 3, while 4 + 4 = 8.

Both failures come from the same cause: taking the biggest coin is a choice that cannot be undone, and the problem does not satisfy the greedy-choice property. The exchange argument breaks because replacing coins of a larger denomination by smaller ones can need a different number of coins. Use dynamic programming whenever the coin system is not known to be canonical.

1static int greedyCoins(int[] coins, int amount) {         // coins sorted in descending order; -1 if stuck
2    int count = 0;
3    for (int c : coins) {
4        count += amount / c;                                // as many of the biggest coin as fit
5        amount %= c;
6    }
7    return amount == 0 ? count : -1;
8}

The dynamic programming solution computes the minimum number of coins for **every** amount from 0 up to the target: dp[a] = 1 + min(dp[a - c]) over the coins c not larger than a, with dp[0] = 0. It compares all choices of last coin instead of committing to the largest, so it is correct for any coin system.

The “Greedy fails: 3 + 3” preset fills the table for coins {1, 3, 4} and amount 6, ending with 2 coins, and traces the answer back as [3, 3]. The animation also counts combinations (the “Count combinations” preset) and reports an impossible amount as -1. The price for the correctness is O(amount × coins) time against greedy's O(coins).

1static int dpCoins(int[] coins, int amount) {
2    int[] dp = new int[amount + 1];
3    Arrays.fill(dp, Integer.MAX_VALUE);
4    dp[0] = 0;
5    for (int a = 1; a <= amount; a++) {
6        for (int c : coins) {
7            if (c <= a && dp[a - c] != Integer.MAX_VALUE) dp[a] = Math.min(dp[a], dp[a - c] + 1);
8        }
9    }
10    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
11}

1static int minCoins(int[] coins, int amount) {
2    int INF = amount + 1;
3    int[] dp = new int[amount + 1]; Arrays.fill(dp, INF); dp[0] = 0;             // dp[a] = fewest coins that make a
4    for (int a = 1; a <= amount; a++)
5        for (int c : coins)
6            if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;          // one coin c, then solve a - c
7    return dp[amount] >= INF ? -1 : dp[amount];
8}
9static long ways(int[] coins, int amount) {
10    long[] dp = new long[amount + 1]; dp[0] = 1;                                 // one way to make 0: take nothing
11    for (int c : coins)                                                          // coins in the outer loop: each combination is counted once
12        for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
13    return dp[amount];
14}