Lesson 33.1 · Greedy Algorithms

When Greedy Works (and When It Doesn't)

Greedy is correct when you can show some optimal answer makes the same first choice (exchange argument), or that greedy is never behind (stays ahead). Otherwise use DP.

14 min

Think of it like this

Giving change with the largest coin first works with euros and dollars because of how those coin values are chosen. With coins of 1, 3 and 4, it fails: for 6 it gives 4 + 1 + 1, while 3 + 3 uses fewer coins.

1.Two proof patterns

Exchange argument: take any optimal solution that differs from greedy's first choice. Swap in greedy's choice and show the solution is still valid and no worse. Repeating this turns any optimal solution into greedy's. Example: Assign Cookies (give the smallest sufficient cookie to the least greedy child).

Greedy stays ahead: show that after every step, greedy's partial result is at least as good as any other algorithm's after the same number of steps. Example: picking intervals by earliest end time (Module 15).

If you can't find a proof, try small counterexamples. If one breaks greedy, switch to DP (Modules 28–32).

Main.java

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] coins = {4, 3, 1};                       // largest first
        int amount = 6, left = amount, greedyCount = 0;
        for (int c : coins) { greedyCount += left / c; left %= c; }

        int[] best = new int[amount + 1];
        Arrays.fill(best, Integer.MAX_VALUE);
        best[0] = 0;
        for (int a = 1; a <= amount; a++)
            for (int c : coins) if (c <= a && best[a - c] != Integer.MAX_VALUE) best[a] = Math.min(best[a], best[a - c] + 1);

        System.out.println("greedy: " + greedyCount + " coins");
        System.out.println("optimal (DP): " + best[amount] + " coins");
    }
}

Output

greedy: 3 coins
optimal (DP): 2 coins

Remember

Prove it: exchange or stays ahead.
Look for a small counterexample.
No proof and a counterexample → DP.

Common mistakes

Trusting greedy because it passes the examples.

Words used in this lesson

Greedy choice: The locally best option at the current step.
Exchange argument: A proof that swapping an optimal solution's choice for greedy's never makes it worse.

Command Palette

When Greedy Works (and When It Doesn't)

1.Two proof patterns