Coin systems: when greedy coin change is optimal

Why it matters

A cashier who hands back 67 cents uses a simple rule. Take the biggest coin that fits, then repeat with what is left. This rule is called greedy, because it always grabs the largest choice now. For the US and UK coin sets, the rule gives the fewest coins. For other coin sets, it can give too many coins, and nothing in the output tells you so.

This lesson teaches you to test a coin set. You will write a program that finds the true best answer, compares it with the greedy answer, and reports the first amount where they differ. That amount is a counterexample: one case that proves the greedy rule wrong for that coin set.

Words you will need

• Coin system: the list of coin values available, such as 1, 5, 10 and 25 cents.
• Change-making problem: pay an exact amount using the fewest coins.
• Greedy: at each step, take the largest coin that still fits.
• Canonical coin system: a coin set for which greedy uses the fewest coins for every amount.
• Counterexample: one amount where greedy uses more coins than the best answer.
• Dynamic programming: a method that solves a problem by solving smaller versions first and storing each answer. Here it finds the best coin count for every amount up to a limit.
• Vector: a resizable list in C++, written std::vector.
• Optional: a C++ type that holds either a value or nothing. std::optional<int> can hold an amount, or nothing when no counterexample exists.
• Bound: a number that tells you how far a test must go. Past the bound, no new failures can appear.

The greedy rule by hand

Pay 67 cents with the US coins 25, 10, 5 and 1.

1. Start with 67. The largest coin that fits is 25. Take it. 42 is left.
2. 42 is still at least 25. Take another 25. 17 is left.
3. 17 is less than 25, so skip it. 10 fits. Take it. 7 is left.
4. 7 is less than 10, so skip it. 5 fits. Take it. 2 is left.
5. 2 is less than 5, so skip it. 1 fits. Take it. 1 is left.
6. Take the last 1.

The coins used are 25, 25, 10, 5, 1 and 1. That is 6 coins. The rule was simple to follow, and it needed no thought about the rest of the amount.

Greedy in C++

The greedy rule needs the coins sorted from largest to smallest. The function below walks the list in that order. For each coin, it takes that coin again and again while the amount is still at least that coin.

std::vector<int> greedy_coins(const std::vector<int>& coins_desc, int amount) {
    std::vector<int> used;
    for (int coin : coins_desc) {
        while (amount >= coin) {
            used.push_back(coin);
            amount -= coin;
        }
    }
    return used;
}

Run on 67 cents, it returns the same six coins as the hand method. The first lines of the program below show this result.

Finding the true best answer

To test greedy, you need the true best answer for many amounts. Dynamic programming gives it. Let best[x] be the fewest coins that make the amount x. Start with best[0] equal to 0, because zero coins make zero cents. For every other amount x, try each coin c that fits. Using coin c leaves x - c to pay, and that part is already known. So the candidate count is best[x - c] + 1. Take the smallest candidate.

Here is a small table for the coins 1, 3 and 4.

Check the amount 6. Coin 1 gives best[5] + 1 = 3. Coin 3 gives best[3] + 1 = 2. Coin 4 gives best[2] + 1 = 3. The smallest is 2, from 3 + 3.

Greedy on the same amount takes 4 first, then 1, then 1. That is 3 coins. The two answers differ, so 6 is a counterexample for the coins 1, 3 and 4.

The C++ code for the table is below. The variable inf is a very large number that means "not reachable yet".

std::vector<int> best_counts(const std::vector<int>& coins, int max_amount) {
    const int inf = std::numeric_limits<int>::max() / 2;
    std::vector<int> best(max_amount + 1, inf);
    best[0] = 0;
    for (int x = 1; x <= max_amount; ++x) {
        for (int coin : coins) {
            if (coin <= x && best[x - coin] + 1 < best[x]) {
                best[x] = best[x - coin] + 1;
            }
        }
    }
    return best;
}

The division by 2 keeps inf + 1 from overflowing, so the comparison best[x - coin] + 1 < best[x] stays safe.

What the table costs

The table has one entry per amount, and each entry tries every coin once. For an amount N and m coins, the work is about N times m steps. For 10,000 cents and eight coins, that is 80,000 steps, a small job for a computer. The table also stores one number per amount, so 10,000 cents needs 10,001 numbers.

The checker builds the table only up to the bound, which is the sum of the two largest coins. For the UK set that is 300, so the table has 301 entries. The check stays cheap even when the coins are large.

The table also works for coin sets that greedy gets wrong. It gives the exact best count for any amount you need. It becomes slow and memory-hungry when the amount is very large, for example billions of cents, because the table grows with the amount. Greedy is faster, but it is only correct for canonical sets, so use the table when you do not know that a set is canonical.

How far must the test go?

Testing every amount is impossible, because there are infinitely many. The answer comes from a known result by Kozen and Zaks (1994). It says that if greedy fails for any amount, the smallest such amount is less than the sum of the two largest coins. So the test only needs to run up to that sum. If greedy passes every amount up to that sum, it passes every amount at all.

The result assumes the coin 1 is in the set, as every example in this lesson does. The check is written for that case.

Take the coins 1, 20 and 21. The two largest coins are 21 and 20, and their sum is 41. A test up to 30 passes, so a quick test would say greedy is fine. The full check up to 41 finds the first failure at 40. The next section shows this.

The full checker

The program below holds the three functions from above. It adds find_counterexample, which runs both methods for every amount up to the bound and returns the first mismatch. Then report prints the result for a coin set. The main function runs nine coin sets.

#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <optional>
#include <vector>
 
// Greedy: take the largest coin that still fits, until the amount is 0.
std::vector<int> greedy_coins(const std::vector<int>& coins_desc, int amount) {
    std::vector<int> used;
    for (int coin : coins_desc) {
        while (amount >= coin) {
            used.push_back(coin);
            amount -= coin;
        }
    }
    return used;
}
 
// Best count for every amount 0..max_amount, found by trying every coin at every step.
std::vector<int> best_counts(const std::vector<int>& coins, int max_amount) {
    const int inf = std::numeric_limits<int>::max() / 2;
    std::vector<int> best(max_amount + 1, inf);
    best[0] = 0;
    for (int x = 1; x <= max_amount; ++x) {
        for (int coin : coins) {
            if (coin <= x && best[x - coin] + 1 < best[x]) {
                best[x] = best[x - coin] + 1;
            }
        }
    }
    return best;
}
 
// Returns the first amount where greedy uses more coins than the best answer.
std::optional<int> find_counterexample(std::vector<int> coins) {
    std::sort(coins.begin(), coins.end(), std::greater<>{});
    const int limit = coins[0] + coins[1];
    const std::vector<int> best = best_counts(coins, limit);
    for (int x = 1; x <= limit; ++x) {
        const auto greedy = greedy_coins(coins, x);
        if (static_cast<int>(greedy.size()) != best[x]) {
            return x;
        }
    }
    return std::nullopt;
}
 
void print_coins(const std::vector<int>& coins) {
    std::cout << "[";
    for (std::size_t i = 0; i < coins.size(); ++i) {
        std::cout << (i ? ", " : "") << coins[i];
    }
    std::cout << "]";
}
 
void report(const std::vector<int>& coins) {
    std::cout << "coins ";
    print_coins(coins);
    std::cout << ": ";
    if (auto x = find_counterexample(coins)) {
        std::vector<int> sorted = coins;
        std::sort(sorted.begin(), sorted.end(), std::greater<>{});
        auto greedy = greedy_coins(sorted, *x);
        auto best = best_counts(coins, *x);
        std::cout << "greedy fails at amount " << *x << ", greedy gives ";
        print_coins(greedy);
        std::cout << " (" << greedy.size() << " coins), best is " << best[*x] << " coins\n";
    } else {
        std::cout << "greedy is optimal for every amount up to the bound\n";
    }
}
 
int main() {
    std::cout << "67 cents with US coins: ";
    print_coins(greedy_coins({25, 10, 5, 1}, 67));
    std::cout << "\n";
    report({1, 5, 10, 25});
    report({1, 2, 5, 10, 20, 50, 100, 200});
    report({1, 3, 4});
    report({1, 5, 6, 9});
    report({1, 5, 7});
    report({1, 20, 21});
    report({1, 2, 3});
    report({1, 2, 5});
    report({1, 2, 4, 8});
    return 0;
}

Save the program as coins.cpp. Compiling turns the source code into a program the computer can run. Use the commands below to compile and run it. The -Wall flag turns on the common warnings, and -std=c++20 selects the C++ version.

g++ -std=c++20 -Wall -o coins coins.cpp
./coins

The output is:

67 cents with US coins: [25, 25, 10, 5, 1, 1]
coins [1, 5, 10, 25]: greedy is optimal for every amount up to the bound
coins [1, 2, 5, 10, 20, 50, 100, 200]: greedy is optimal for every amount up to the bound
coins [1, 3, 4]: greedy fails at amount 6, greedy gives [4, 1, 1] (3 coins), best is 2 coins
coins [1, 5, 6, 9]: greedy fails at amount 11, greedy gives [9, 1, 1] (3 coins), best is 2 coins
coins [1, 5, 7]: greedy fails at amount 10, greedy gives [7, 1, 1, 1] (4 coins), best is 2 coins
coins [1, 20, 21]: greedy fails at amount 40, greedy gives [21, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] (20 coins), best is 2 coins
coins [1, 2, 3]: greedy is optimal for every amount up to the bound
coins [1, 2, 5]: greedy is optimal for every amount up to the bound
coins [1, 2, 4, 8]: greedy is optimal for every amount up to the bound

The program compiles without warnings under -Wall. The first line matches the hand calculation for 67 cents.

Reading one report line

Take the line for [1, 3, 4]. The text after the colon says where the check failed.

• "greedy fails at amount 6" means 6 is the smallest amount where greedy uses more coins than the best answer.
• "greedy gives [4, 1, 1] (3 coins)" lists the coins greedy picked, so you can add them up by hand.
• "best is 2 coins" is the value from the table for amount 6.

The report prints only the first failure. A coin set can fail at many amounts, but the first one is enough to show that greedy is wrong for that set. The report also prints the count of the best answer, not the coins that make it. Printing those coins needs one more value stored for each table entry, which is a useful exercise to try after this lesson.

Worked example 1: the UK coins

The UK coin set is 1, 2, 5, 10, 20, 50, 100 and 200 pence. The largest two coins are 200 and 100, so the bound is 300. The checker runs every amount up to 300 and finds no mismatch. By the Kozen and Zaks result, greedy is therefore optimal for every amount. The rule works for this set.

A pass here is a proof, not just a sample. A pass up to the bound is the only evidence needed, because a failure below the bound would have been found.

Worked example 2: the coins 1, 5, 6 and 9

This set has a clear failure. Pay 11 with greedy. The largest coin that fits is 9, so take it. 2 is left. Only 1 fits, so take 1, then another 1. That is 9, 1, 1: three coins.

The best answer is 5 and 6, which is two coins. Greedy failed because the big coin 9 looked attractive, but it left an awkward 2 that needed two extra coins. Greedy has no way to see that.

The program reports the first failure at 11. It checks amounts from 1 upward, so it stops at the smallest failure.

Worked example 3: the coins 1, 20 and 21

This example is harder, because the first failure is large. For the amount 40, greedy takes 21, then needs 19 more. It fills the 19 with ones, which is 20 coins in total. The best answer is 20 and 20, which is two coins.

Look at the amounts below 40. For 20, 21, 22 and up to 30, greedy and the best answer agree in coin count. Greedy only fails at 40. A test that stops at 30 would say the set is fine, and it would be wrong.

The sum of the two largest coins is 41. The check runs to 41, and it finds the failure at 40. This is the reason the code uses coins[0] + coins[1] as its limit, and not a small fixed number such as 20.

Worked example 4: 10 cents with the coins 1, 5 and 7

Greedy takes the 7 first, because it is the largest coin that fits. That leaves 3 cents, and greedy pays them with three 1s. The total is four coins: 7, 1, 1 and 1.

The best answer is two 5s. The 7 looked good, but it left an awkward 3 that cost three coins. The bound for this set is 7 + 5 = 12, and the checker finds the first failure at 10. The program output above shows the same result.

Common mistakes

The coin list is not sorted from largest to smallest. The greedy function visits coins in the order it receives them. If the list is {1, 3, 4} and the code runs greedy on it without sorting, the 1 is tried first, so the code takes ones before it ever reaches the 4. The program below shows the effect.

#include <iostream>
#include <vector>
 
std::vector<int> greedy_coins(const std::vector<int>& coins_desc, int amount) {
    std::vector<int> used;
    for (int coin : coins_desc) {
        while (amount >= coin) {
            used.push_back(coin);
            amount -= coin;
        }
    }
    return used;
}
 
int main() {
    // Mistake 1: coins not sorted from largest to smallest.
    auto a = greedy_coins({1, 3, 4}, 6);
    std::cout << "unsorted: " << a.size() << " coins\n";
 
    // Mistake 2: no coin of value 1, so greedy can stop short.
    auto b = greedy_coins({5, 10}, 6);
    int used_total = 0;
    for (int c : b) used_total += c;
    std::cout << "no 1-coin: used " << used_total << " of 6\n";
    return 0;
}

Its output is:

unsorted: 6 coins
no 1-coin: used 5 of 6

With the list in the wrong order, greedy takes the 1 six times and returns 6 coins for an amount that needs 2. The fix is to sort first, as find_counterexample does with std::sort and std::greater<>{}.

The coin 1 is missing. In the second case, greedy takes a 5 and then stops, because 1 cent is left and neither 5 nor 10 fits. The function returns a partial answer and does not signal an error. Check the total you paid, or require the coin 1 before you test a set.

The test stops too early. The coins 1, 20 and 21 pass a check up to 30 and fail at 40. A test with a small fixed limit can pass a bad coin set. Use the bound coins[0] + coins[1] from the program.

An unsigned comparison gives a warning. The code below loops with an int index over a vector. The vector's size() returns an unsigned type, which holds only zero and positive numbers, so the compiler warns.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> v{1, 2};
    for (int i = 0; i < v.size(); ++i) std::cout << v[i];
}

Saved as sign_check.cpp and compiled with g++ -std=c++20 -Wall sign_check.cpp, the compiler reports (the wording depends on the compiler version):

sign_check.cpp: In function ‘int main()’:
sign_check.cpp:6:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    6 |     for (int i = 0; i < v.size(); ++i) std::cout << v[i];
      |                     ~~^~~~~~~~~~

The warning does not stop the program, but it can hide real bugs. Use a range-based loop, for (int coin : coins), or declare the index as std::size_t.

Calling a short pass a proof. Greedy passing up to a small limit is not a proof. Only a pass up to the bound says the rule holds for every amount.

Practice

Exercise 1. Is the coin set 1, 2 and 3 canonical? Use the bound to decide how far to check.

Show the answer

The two largest coins are 3 and 2, so the bound is 5. Check the amounts 1 to 5.

• Amount 1: greedy takes 1. The best is 1. Same.
• Amount 2: greedy takes 2. The best is 1. Same.
• Amount 3: greedy takes 3. The best is 1. Same.
• Amount 4: greedy takes 3, then 1. That is 2 coins. The best is 2 coins, such as 2 and 2. Same.
• Amount 5: greedy takes 3, then 2. That is 2 coins. The best is 2 coins. Same.

Greedy matches the best count at every amount up to 5, so the set is canonical. The program prints "greedy is optimal for every amount up to the bound" for this set, which is the same result.

Exercise 2. Find the smallest amount where greedy fails for the coins 1, 4 and 6.

Show the answer

Greedy and the best count agree for amounts 1 to 7. At 8, greedy takes 6, then 1, then 1. That is 3 coins. The best answer is 4 and 4, which is 2 coins. So the smallest failure is 8. The bound is 4 + 6 = 10, so 8 is below the bound, as the theorem requires.

Exercise 3. The coins are 2 and 5, with no coin 1. Explain what greedy does with the amount 3, and why the bound check cannot be used directly.

Show the answer

Greedy skips the 5, because it is bigger than 3, and takes one 2. One unit is left, and no coin of value 1 exists, so greedy returns the coin 2 and leaves 1 unpaid. The amount 3 cannot be paid with these coins at all. The bound check assumes a coin 1 exists, so a coin set without it must be rejected first.

Exercise 4. In find_counterexample, change the limit to coins[0], the largest coin only. What does the function return for the coins 1, 3 and 4?

Show the answer

The limit becomes 4, so the loop checks amounts 1 to 4. For those amounts, greedy and the best count agree: 1 gives 1 coin, 2 gives 2 coins, 3 gives 1 coin, and 4 gives 1 coin. The function returns no counterexample, which is std::nullopt. This is wrong, because 6 is a counterexample for these coins. The bound must be the sum of the two largest coins, not the largest coin alone.

Exercise 5. For the coins 1, 5, 6 and 9, what is the smallest amount where greedy fails, and what line does the report print for this set?

Show the answer

The smallest failure is 11. Greedy takes 9, then 1 and 1, which is 3 coins. The best answer is 5 and 6, which is 2 coins. The report prints coins [1, 5, 6, 9]: greedy fails at amount 11, greedy gives [9, 1, 1] (3 coins), best is 2 coins. This is the same line as in the program output above.

Summary

• Greedy takes the largest coin that fits, and it needs the coins sorted from largest to smallest.
• Dynamic programming gives the true best count for every amount, by storing each smaller answer.
• A coin set is canonical when greedy matches the best count for every amount.
• If greedy fails, the smallest failure is below the sum of the two largest coins, so that sum is the bound.
• The checker runs both methods up to the bound and reports the first mismatch, which is a counterexample.