Greedy Algorithms in C: When Coin Change Fails vs DP

Revised November 2026. This tutorial first appeared in Korean in 2021. We recompiled its C example with Apple clang 21 (-Wall -Wextra -fsanitize=address,undefined). It produced no warnings, but it printed garbage when the input was empty, and two claims in the text were only half right: that greedy change-making requires each coin to be a multiple of the smaller ones, and that greedy solves the knapsack problem. This version adds a greedy-vs-DP comparison over 2,000 amounts, activity selection with a proof sketch, and a decision rule for when greedy is safe.

This article is for programmers who wrote "just take the biggest one first" and then hit an input where the answer was wrong. The short answer: a greedy algorithm is guaranteed optimal only when you can show both the greedy-choice property and optimal substructure. When the proof is not obvious, the quickest check is to compare greedy against dynamic programming or brute force on small inputs, and we show how few inputs that takes for coin systems.

The idea: take the best-looking option, never look back

A greedy algorithm builds an answer step by step. At each step it picks the option that looks best right now and never revisits that decision. It does not look ahead, which makes it fast and short to write. Whether those locally best choices add up to a globally best answer depends entirely on the problem.

The textbook example is making change with as few coins as possible. Suppose the coins are 1, 7 and 10, and you owe 14. Greedy takes the largest coin that fits: 10, then 1, 1, 1, 1, for five coins. Two 7s would do it with two. Once greedy took the 10, the better answer was out of reach.

Re-running the 2021 example

The 2021 program subtracted one coin at a time from the amount. It still compiles cleanly as both C and C++, and the documented inputs give the documented output (we translate the Korean output here):

$ echo 14 | ./greedy2021
10-unit coins: 1, 7-unit coins: 0, 1-unit coins: 4

The bug shows up with bad input. The program never checks the return value of scanf, so when stdin is empty or not a number, it computes with an uninitialized m. Three runs with empty input printed 10-unit counts of 1,467,678, 4,968,939 and 4,092,395. Reading an uninitialized local is undefined behavior, and neither -Wall -Wextra nor AddressSanitizer and UBSan flagged it. The fix is to check input first: if (scanf("%d", &m) != 1 || m < 0). The program also answered "no solution" for an amount of 0, which is payable with zero coins.

Below are the corrected greedy function and a DP function that computes the true minimum for the same amount. Greedy now uses division instead of subtracting one coin per loop iteration.

/* coins sorted from largest to smallest */
static int greedy(const int *c, int n, int amount, int used[])
{
    int total = 0;
    for (int i = 0; i < n; i++) {
        used[i] = amount / c[i];
        amount -= used[i] * c[i];
        total += used[i];
    }
    return amount == 0 ? total : -1;          /* -1: cannot pay exactly */
}

/* dp[a] = minimum number of coins for amount a */
static int dp_min(const int *c, int n, int amount)
{
    static int dp[MAXA + 1];
    dp[0] = 0;
    for (int a = 1; a <= amount; a++) {
        dp[a] = INT_MAX;
        for (int i = 0; i < n; i++)
            if (c[i] <= a && dp[a - c[i]] != INT_MAX && dp[a - c[i]] + 1 < dp[a])
                dp[a] = dp[a - c[i]] + 1;
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

Coin change: where greedy is optimal and where it fails

Same amounts through both functions, built with clang -std=c17 -Wall -Wextra -fsanitize=address,undefined (zero warnings):

{500,100,50,10} amount 1260: greedy 6 coins (500x2 100x2 50x1 10x1), DP 6 coins
{4,3,1}        amount    6: greedy 3 coins (4x1 3x0 1x2), DP 2 coins
{10,7,1}       amount   14: greedy 5 coins (10x1 7x0 1x4), DP 2 coins
{25,10,5,1}    amount   30: greedy 2 coins (25x1 10x0 5x1 1x0), DP 2 coins
{25,15,1}      amount   30: greedy 6 coins (25x1 15x0 1x5), DP 2 coins

With a 500/100/50/10 system, 1,260 takes six coins either way. With {4,3,1} and an amount of 6, greedy picks 4+1+1 while DP finds 3+3. A single amount proves little, so we compared every amount from 1 to 2,000:

{500,100,50,10}        1..2000: greedy != DP for   0 amounts
{25,10,5,1}            1..2000: greedy != DP for   0 amounts
{4,3,1}                1..2000: greedy != DP for 499 amounts (first: 6)
{10,7,1}               1..2000: greedy != DP for 597 amounts (first: 14)
{25,15,1}              1..2000: greedy != DP for 1185 amounts (first: 30)

This corrects the 2021 text, which said the larger coins must be multiples of the smaller ones for greedy to work. A divisibility chain is enough, but it is not required. In US coins, 25 is not a multiple of 10, and greedy was still optimal on all 2,000 amounts. A coin system where greedy is always optimal is called canonical.

You also do not need to test forever. A result by Kozen and Zaks (1994) says that if a coin system has a counterexample at all, the smallest one is below the sum of the two largest coins. Our data agree: the first failure for {4,3,1} is 6 (below 7), for {10,7,1} it is 14 (below 17), and for {25,15,1} it is 30 (below 40). If you design denominations for a game or an in-app currency, a DP comparison up to that bound tells you whether greedy change-making is safe.

Activity selection, with a proof sketch

Activity selection is the classic problem where greedy provably works. One meeting room, many requests with fixed start and end times; schedule as many non-overlapping meetings as possible. The 2021 post used an interval diagram of unclear origin, so we removed it and built our own set of 11 meetings as half-open intervals [start, end). We ran three sorting rules through the same code and computed the true optimum by checking all 2^11 subsets.

/* sort by a rule, then accept each activity that does not overlap a chosen one */
static int greedy(const Act *src, int n, int (*rule)(const void *, const void *),
                  const char *label)
{
    Act a[16], chosen[16];
    int k = 0;
    for (int i = 0; i < n; i++) a[i] = src[i];
    qsort(a, (size_t)n, sizeof a[0], rule);
    for (int i = 0; i < n; i++) {
        int ok = 1;
        for (int j = 0; j < k; j++)
            if (overlap(&a[i], &chosen[j])) { ok = 0; break; }
        if (ok) chosen[k++] = a[i];
    }
    /* … print chosen[0..k) … */
    return k;
}

11 meetings (optimum by brute force: 4)
  earliest end  : A[1,4) D[5,7) H[8,11) K[12,16)  -> 4
  earliest start: C[0,6) G[6,10) K[12,16)  -> 3
  shortest      : B[3,5) D[5,7) H[8,11) K[12,16)  -> 4
long one starts first (optimum by brute force: 3)
  earliest end  : M[1,3) N[4,6) O[7,9)  -> 3
  earliest start: L[0,10)  -> 1
  shortest      : M[1,3) N[4,6) O[7,9)  -> 3
short one in the middle (optimum by brute force: 2)
  earliest end  : P[0,5) R[6,11)  -> 2
  earliest start: P[0,5) R[6,11)  -> 2
  shortest      : Q[4,7)  -> 1

"Earliest start" collapses to one meeting when a long meeting starts first. "Shortest first" collapses when a short meeting straddles two others. Only "earliest end" was optimal in all three cases, and the proof is short:

1. Greedy-choice property (exchange argument). Let g be the meeting that ends first, and take any optimal schedule O. Replace the first-ending meeting o in O with g. Since g ends no later than o, it cannot overlap anything else in O, all of which starts after o ends. The count is unchanged, so this is still optimal. Some optimal schedule therefore always contains g.
2. Optimal substructure. After choosing g, what remains is "pick as many meetings as possible among those starting at or after g ends", which is the same problem on a smaller input.
3. By induction, repeatedly picking the earliest-ending compatible meeting is optimal. In practice you sort by end time (O(n log n)) and make one pass, keeping only the last end time; the full overlap check in the code above exists only so that the losing rules can be compared fairly.

Deciding when greedy is safe

The two steps of that proof are the general test.

• Greedy-choice property: can you show, usually by an exchange argument, that taking the locally best option never rules out an optimal solution? For coins {4,3,1} and an amount of 6, taking the 4 first rules out 3+3, so the property fails there.
• Optimal substructure: after the choice, is the rest a smaller instance of the same problem whose optimum combines into the overall optimum? Coin change does have this property, which is exactly why DP solves it.
• If you cannot prove it: test. Comparing against DP over 2,000 amounts, or brute-forcing 2^11 subsets, took a few dozen lines and ran instantly.

The 2021 post also listed Dijkstra's shortest paths, minimum spanning trees and the knapsack problem as greedy applications. Dijkstra (with non-negative edge weights) and Kruskal's or Prim's MST algorithms are indeed provably optimal greedy algorithms. Knapsack is greedy-optimal only when items can be split. With weights 10, 20, 30, values 60, 100, 120 and capacity 50:

0/1 greedy by ratio: 160, 0/1 optimum: 220, fractional greedy: 240

Taking whole items by value-per-weight gives 160; the real 0/1 optimum (the 20 and 30 items) is 220. If the last item may be cut, the same order gives 240, which is optimal for the fractional problem. The 0/1 version needs DP.

Summary

• Greedy algorithms are fast and simple, but optimality has to be proved per problem.
• For change-making, 500/100/50/10 and US coins never failed in our test; {4,3,1}, {10,7,1} and {25,15,1} failed on hundreds of amounts. Divisibility is not a requirement.
• Any counterexample appears below the sum of the two largest coins, so a short DP comparison settles the question.
• For activity selection, only "earliest end time first" is optimal, and an exchange argument proves it.
• Related posts we re-verified the same way: sorting algorithms, binary search and linear search.