When greedy fails

A greedy rule is easy to invent and easy to believe. Many are wrong. This lesson shows typical failures, a test that decides when the “largest coin first” rule is safe, a cheap way to catch a wrong rule before trusting it, and the structure that makes greedy always right.

Counterexamples

A counterexample is one input on which the rule gives a worse answer than the best one. One counterexample is enough to show that a rule is wrong (CORR-4). The figure shows two.

• Coins 1, 3 and 4. The largest coin first makes 6 as 4 + 1 + 1, but 3 + 3 uses two coins. Taking the 4 first leaves 2, which needs two 1s.
• Whole items. Lesson 1’s rule (the most value per kg) fails when items cannot be cut. The exchange in lesson 2 moved one kilogram at a time, and that is not allowed here.

Other well-known failures:

• Bookings with values (lesson 3): ends first ignores the money.
• Visiting every city on the shortest round trip: always going to the nearest city not yet visited can produce a trip far longer than the best one.
• Colouring a map with the fewest colours by giving each region the first colour its neighbours do not use: the answer depends on the order, and can be far from the fewest.

In every case, a choice that looked best now removed a better choice later, and greedy never goes back. That is the difference from dynamic programming, which keeps the best answer for every smaller problem, and from backtracking, which tries the other choices.

Which coin systems are safe

A coin system is called canonical when the largest coin first gives the fewest coins for every amount. India’s coins and notes (1, 2, 5, 10, 20, 50, 100, 200, 500) are canonical, and so are most countries’. The system 1, 3, 4 is not.

Checking every amount is impossible: there are infinitely many. But a theorem by Kozen and Zaks (1994) limits the search. If the system is not canonical, the smallest amount where greedy fails is less than the sum of the two largest coins.

So it is enough to compare the greedy answer with the true fewest number of coins for every amount below that sum. The fewest coins for every amount up to a limit can be found with a short loop, because the best way to make x uses some last coin c, and before it, the best way to make x − c:

def fewest_coins(coins, limit):
    # fewest[x] = the fewest coins that make x, for x < limit
    fewest = [0] * limit
    for x in range(1, limit):
        fewest[x] = 1 + min(fewest[x - c] for c in coins if c <= x)
    return fewest

This assumes a coin of 1, so every amount can be made. It costs O(limit × number of coins). This loop is the first example of dynamic programming, the subject of DYNP: it reuses the answers for smaller amounts instead of searching again.

Testing a greedy idea

Before trying to prove a rule, try to break it. Write a brute force that tries every possible answer, run both on thousands of small random inputs, and compare (CORR-5). Small inputs are enough: almost every wrong rule fails on an input of five or six items, and the program prints it.

import random
from itertools import combinations

def best_by_brute_force(items, cap):
    best = 0
    for k in range(len(items) + 1):
        for pick in combinations(items, k):
            if sum(w for w, v in pick) <= cap:
                best = max(best, sum(v for w, v in pick))
    return best

# greedy(items, cap) is the rule being tested
for trial in range(10_000):
    items = [(random.randint(1, 6), random.randint(1, 9))
             for _ in range(5)]
    if greedy(items, 8) != best_by_brute_force(items, 8):
        print("counterexample:", items)
        break

If the test finds nothing, the rule may still be wrong for larger inputs, so it is not a proof. But a rule that survives is worth trying to prove, with an exchange argument or by showing that greedy stays ahead.

When greedy always works

There is a kind of structure on which greedy is always right. Say some sets of items are allowed, with two rules:

1. every part of an allowed set is allowed (taking an item out never breaks anything);
2. if one allowed set is smaller than another, some item of the larger one can be added to the smaller one, and the result is still allowed.

Such a structure is called a matroid. For a matroid, this greedy method finds the allowed set with the largest total weight, whatever the weights are: go through the items from heaviest to lightest, and add each one that keeps the set allowed. The proof is an exchange argument that uses rule 2.

• A matroid: the sets of edges of a graph that contain no loop. That is why Kruskal’s method, which takes edges from cheapest to most expensive and skips any that close a loop, finds a cheapest spanning tree (SPAN-2).
• Not a matroid: the sets of items that fit in a bag. One heavy item fits, and so do two light ones; but neither light item can be added to the heavy one. Rule 2 fails, and so does greedy.

Interval scheduling and Huffman coding are not matroids, yet greedy works for them: their own exchange arguments do the job. A matroid is a sufficient reason for greedy to work, not the only one.

What to do instead

• Dynamic programming (DYNP): when the problem breaks into smaller problems of the same kind, keep the best answer to each, as the coin loop above does. The 0/1 knapsack, coin change and bookings with values are all solved this way.
• Backtracking with pruning (RECR-5): try the choices, and stop early when a branch cannot beat the best answer found. A greedy answer is a good first “best so far”.
• Greedy as an approximation (HARD-4): for some hard problems greedy cannot be best, but it is provably close. For the 0/1 knapsack, the better of “greedy by value per kg” and “the single most valuable item that fits” is always at least half of the best.