Greedy Concepts

A greedy algorithm builds a solution through a sequence of choices, and at each step it takes whatever looks best right now, never revisiting that decision. Unlike exhaustive search, which tries every option, or dynamic programming, which tabulates answers to subproblems, a greedy algorithm follows a single path. That makes it short and fast, but you have to prove separately that the path actually leads to an optimal answer.

Vocabulary

A greedy algorithm is correct when the greedy choice property and optimal substructure both hold. The first guarantees that the first choice is never a mistake; the second guarantees that the rest of the problem can be solved the same way. Together they give an inductive proof that every choice is safe.

How an exchange argument goes

The exchange argument is the workhorse of greedy proofs, and it almost always has the same shape.

1. Take an arbitrary optimal solution OPT.
2. Find the first place where OPT differs from the greedy solution.
3. Show that replacing OPT's element there with the greedy element keeps the solution valid and no worse.
4. Repeating the swap turns OPT into the greedy solution, so the greedy solution is optimal too.

Take the problem of choosing as many non-overlapping meetings as possible, where greedy picks the meeting that finishes first. Replace the first meeting of any optimal schedule with the earliest-finishing one: the new meeting ends no later than the old one, so it cannot collide with anything that followed. The count is unchanged, so the swap costs nothing.

When greedy works: making change

Paying out change with the largest coins first is the most familiar greedy algorithm. In a well-designed coin system such as US coins (1, 5, 10, 25 cents) it always uses the fewest coins.

def greedy_coins(coins, amount):
    """Use as many large coins as possible. None if the amount cannot be made."""
    count = 0
    for coin in sorted(coins, reverse=True):
        take, amount = divmod(amount, coin)
        count += take
    return count if amount == 0 else None


print(greedy_coins([1, 5, 10, 25], 63))  # 6 (25 * 2 + 10 + 1 * 3)

When greedy fails: a counterexample

Now suppose the coins are 1, 3 and 4 and you owe 6. Greedy grabs a 4 and then two 1s, three coins in total. Two 3s would do with only two coins. The first greedy choice (the 4) is not part of any optimal answer, so the greedy choice property is broken. Here you need dynamic programming, which computes the minimum for every amount.

def min_coins(coins, amount):
    """Dynamic programming: best[a] = fewest coins that make a."""
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] + 1 < best[a]:
                best[a] = best[a - c] + 1
    return best[amount] if best[amount] != INF else None


print(greedy_coins([1, 3, 4], 6), min_coins([1, 3, 4], 6))  # 3 2

When the proof is hard: compare on small inputs

Before you write a proof, or whenever you doubt one, the quickest check is to compare the greedy answer with a known-correct one (brute force or dynamic programming) on small inputs. A single counterexample is enough to reject a greedy rule.

def find_counterexample(coins, limit=100):
    for amount in range(1, limit + 1):
        g, d = greedy_coins(coins, amount), min_coins(coins, amount)
        if g != d:
            return amount, g, d
    return None


print(find_counterexample([1, 3, 4]))       # (6, 3, 2)
print(find_counterexample([1, 5, 10, 25]))  # None

Finding no counterexample is not a proof, but it is very effective at discarding wrong rules early.

When to think greedy

• Processing items in sorted order, or in the order a priority queue hands them out, seems natural
• The question asks for a maximum count, a minimum cost or a minimum number, and choices do not interact much
• The data can be ranked by a single key such as an interval end, a deadline or a weight
• A dynamic programming state would be too large and you need a simpler rule

Summary

• A greedy algorithm takes the best-looking option at every step and never backtracks.
• It is correct when the greedy choice property and optimal substructure hold, usually shown with an exchange argument.
• One counterexample, such as coins 1, 3, 4 and amount 6, is enough to rule a greedy rule out; use dynamic programming instead.
• Comparing against brute force on small inputs filters out wrong rules before you invest in a proof.