Greedy Algorithms

Divide and conquer split the problem and solved every part. This lesson’s approach behaves more boldly: at every step it makes the choice that looks best at that moment, never questions that choice again, and never goes back. The approach is called greedy, and its appeal is obvious — because there is no backtracking, the step count is small.

Boldness has a cost. In divide and conquer, the precondition concerned combining and was visible to the eye. Here the precondition is far more hidden: the locally best choice must be part of the globally best solution. This cannot be seen by looking at the input; it is either proven or wrong. This lesson establishes what the proof is and counts how wrong things go when there is none.

• DA20. The measured problem: paying a given amount with the fewest coins in a coin system.
• DA21. A coin system has the form $(1, a, b, c)$. Having 1 guarantees every amount is payable, so an “unpayable” case does not contaminate the measurement.
• DA22. The greedy procedure starts from the largest coin and never goes back. A step is subtracting one coin from the remainder.
• DA23. The oracle is brute force: it counts every combination of coins. The bottom-up solution is tested against the oracle before being used in place of it.
• DA24. The sweep covers every triple between 2 and 20 — 969 systems — and tries every amount from 1 to 50 in each system.
• DA25. A diverging input here is a system: one where greedy gives too many coins for at least one amount is counted.
• DA26. Excess is greedy’s coin count minus the minimum.
• DA27. The greedy procedures from M01/K04 — Dijkstra’s algorithm, minimum spanning tree algorithms, and Huffman coding — are not repeated; only why they do not go wrong is written.
• DA28. The second corpus is five-value systems generated with seed 20260219.

Greedy Choice and the Burden of Proof

A greedy procedure builds a solution step by step, and at each step it takes whichever candidate looks best by some measure. The measure is fixed, and the choice is never undone. For such a procedure to be correct, it suffices to show a single thing: the choice made at every step is present in at least one of the optimal solutions. This is called the greedy choice property, and it is shown in almost the same way every time — an exchange argument.

The Algorithms course established and proved three examples of this reasoning. In the minimum spanning tree lesson, the cut property showed that the lightest edge crossing a cut is present in some optimal tree: adding that edge to a tree that lacks it creates a cycle, from which a heavier edge crossing the same cut can be removed. In the Huffman Coding lesson, the same structure showed that the two rarest symbols can be made siblings. In Dijkstra’s algorithm, the choice was that the unsettled node with the smallest estimate becomes settled, and this rested on edge weights being non-negative.

What the three share is that the choice’s safety was shown. This lesson does not repeat those procedures; the question it asks is what happens when there is no proof. The answer is something countable.

Verifying the Oracle

The procedure that gives the fewest coins for the change-making problem is the bottom-up solution. But this course’s rule requires the oracle to be brute force. This is why the bottom-up solution is tested against the oracle before being used in the broad sweep.

# Shared framework: step counter (same as the previous lessons).
from itertools import combinations


class Counter:
    def __init__(self):
        self.steps = 0

    def add(self, n=1):
        self.steps += n


def greedy_coins(system, amount, s):
    """Starts from the largest coin, never goes back."""
    remaining, count = amount, 0
    for p in sorted(system, reverse=True):
        while remaining >= p:
            s.add()
            remaining -= p
            count += 1
    return count if remaining == 0 else None


def dp_coins(system, amount, s):
    """Exact bottom-up solution."""
    best = [0] + [10**9] * amount
    for t in range(1, amount + 1):
        for p in system:
            if p <= t:
                s.add()
                if best[t - p] + 1 < best[t]:
                    best[t] = best[t - p] + 1
    return best[amount] if best[amount] < 10**9 else None


def oracle_brute_coins(system, amount, s):
    """Counts every combination of coins. This is the oracle."""
    best = None

    def visit(i, remaining, count):
        nonlocal best
        s.add()
        if remaining == 0:
            if best is None or count < best:
                best = count
            return
        if i == len(system):
            return
        p = system[i]
        for k in range(remaining // p + 1):
            visit(i + 1, remaining - k * p, count + k)
    visit(0, amount, 0)
    return best


EXAMPLES = [(1, 3, 7, 12), (1, 4, 9, 16), (1, 5, 10, 25), (1, 18, 19, 20)]
diverging, oc, dc = 0, Counter(), Counter()
for system in EXAMPLES:
    for amount in range(1, 26):
        if oracle_brute_coins(system, amount, oc) != dp_coins(system, amount, dc):
            diverging += 1
print("verification: ", len(EXAMPLES), "systems x 25 amounts =", len(EXAMPLES) * 25, "inputs")
print("oracle (brute force) steps:", oc.steps, "| bottom-up steps:", dc.steps,
      "| ratio:", round(oc.steps / dc.steps, 2))
print("diverging from oracle:", diverging)

verification:  4 systems x 25 amounts = 100 inputs
oracle (brute force) steps: 13584 | bottom-up steps: 2785 | ratio: 4.88
diverging from oracle: 0

There is no divergence in any of the hundred inputs; brute force spends 13,584 steps, the bottom-up solution 2785. This does not prove the bottom-up solution correct — testing is not proof — but it puts using it in place of the oracle in the 969-system sweep on measured ground. The reason brute force is not used directly is also visible: the 4.88-times gap is harmless over 100 inputs, but for 969 systems and 50 amounts it would needlessly inflate the sweep.

Nine Hundred Sixty-Nine Systems

The main measurement sweeps every four-value system.

# Continuing from the previous block: Counter, greedy_coins, dp_coins and combinations come from there.
def greedy_sweep(limit=20, amount_limit=50):
    """Every {1,a,b,c} system: in how many systems, and at how many amounts, does greedy give too much."""
    broken, total_systems, largest_excess, example = 0, 0, 0, None
    for a, b, c in combinations(range(2, limit + 1), 3):
        system = (1, a, b, c)
        total_systems += 1
        s = Counter()
        bad = 0
        excess_max = 0
        for t in range(1, amount_limit + 1):
            greedy = greedy_coins(system, t, s)
            dp = dp_coins(system, t, s)
            if greedy is not None and dp is not None and greedy > dp:
                bad += 1
                if greedy - dp > excess_max:
                    excess_max = greedy - dp
        if bad:
            broken += 1
            if excess_max > largest_excess:
                largest_excess = excess_max
                example = (system, bad, excess_max)
    return {"systems": total_systems, "broken": broken,
            "ratio": round(broken / total_systems, 4),
            "largest_excess": largest_excess, "example": example}


result = greedy_sweep()
print("systems swept:", result["systems"], "| greedy gives too much in:", result["broken"],
      "| ratio:", result["ratio"])
print("largest excess:", result["largest_excess"], "| example system:", result["example"])

systems swept: 969 | greedy gives too much in: 827 | ratio: 0.8535
largest excess: 16 | example system: ((1, 18, 19, 20), 2, 16)

On 827 of 969 systems, greedy gives more coins than necessary. The ratio is 0.8535, meaning roughly five-sixths of four-value coin systems are not suited to greedy. The largest excess is 16 coins, seen in the system $(1, 18, 19, 20)$.

This number deserves its due. Greedy choice fits everyone’s intuition in the change-making problem: give the largest coin, shrink the remainder. The intuition is not wrong — it genuinely gives the correct answer on 142 systems. What is wrong is the intuition standing in for a procedure. Greedy choice is a heuristic; it is not a procedure until it is proven.

Where and How Much It Is Wrong

Where the largest excess appears shows the shape of the error.

# Continuing from the previous blocks: Counter, greedy_coins, dp_coins come from there.
SYSTEM = (1, 18, 19, 20)
s = Counter()
print("system", SYSTEM, "- amounts where greedy gives too much")
for amount in range(1, 51):
    greedy = greedy_coins(SYSTEM, amount, s)
    dp = dp_coins(SYSTEM, amount, s)
    if greedy > dp:
        print(f"  amount {amount:2d}: greedy {greedy:2d} coins, minimum {dp:2d} coins,"
              f" excess {greedy - dp:2d}")
print()
print("sweep limit  broken systems  ratio")
for amount_limit in (10, 20, 50, 100):
    result = greedy_sweep(amount_limit=amount_limit)
    print(f"{amount_limit:12d} {result['broken']:15d} {result['ratio']:6.4f}")

system (1, 18, 19, 20) - amounts where greedy gives too much
  amount 36: greedy 17 coins, minimum  2 coins, excess 15
  amount 37: greedy 18 coins, minimum  2 coins, excess 16

sweep limit  broken systems  ratio
          10              85 0.0877
          20             466 0.4809
          50             827 0.8535
         100             827 0.8535

At amount 36, the minimum solution is two coins: 18 plus 18. Greedy instead takes 20, and can only pay the remaining 16 with ones, using 17 coins. The same thing happens at 37: the minimum solution is 18 plus 19, greedy’s solution is 20 plus seventeen ones. The source of the error is visible — taking the largest coin leaves behind a remainder that is expensive to pay. Greedy does not see this remainder, because when making its choice it looks only at the largest value at that moment.

The bottom table says something more unsettling. When the same 969 systems are tested only up to 10, 85 systems look broken, a ratio of 0.0877. Tested up to 20, 466 systems, a ratio of 0.4809. Tested up to 50, 827, a ratio of 0.8535. Going up to 100 changes nothing. So in this system family, every error appears below 50, yet someone testing only up to 10 would think 91 percent of the systems are clean. The scope of testing determines the result itself; calling an approach “tested” means nothing unless it also states tested up to what.

A Testable Sufficient Condition

If a heuristic cannot stand in for a proof, at least a testable condition can be sought. For coin systems, the first candidate that comes to mind is that the values form a divisibility chain: each value divides the next.

# Continuing from the previous block: Counter, greedy_coins, dp_coins, combinations come from there.
chain_clean, chain_broken, other_clean, other_broken = 0, 0, 0, 0
clean_examples = []
for a, b, c in combinations(range(2, 21), 3):
    system = (1, a, b, c)
    s = Counter()
    broken = any(greedy_coins(system, t, s) > dp_coins(system, t, s)
                 for t in range(1, 51))
    chain = b % a == 0 and c % b == 0            # does each value divide the next
    if chain and broken:
        chain_broken += 1
    elif chain:
        chain_clean += 1
    elif broken:
        other_broken += 1
    else:
        other_clean += 1
        if len(clean_examples) < 4:
            clean_examples.append(system)
print("has divisibility chain    : clean", chain_clean, "| broken", chain_broken)
print("no divisibility chain     : clean", other_clean, "| broken", other_broken)
print("examples of clean systems without a chain:", clean_examples)

has divisibility chain    : clean 13 | broken 0
no divisibility chain     : clean 129 | broken 827
examples of clean systems without a chain: [(1, 2, 3, 4), (1, 2, 3, 5), (1, 2, 3, 6), (1, 2, 3, 7)]

Of the 13 systems carrying a divisibility chain, all 13 are clean; under this condition, greedy never gives too much on any amount. But 129 of the systems without a chain are also clean. The condition is sufficient, not necessary: it gives a guarantee when it holds, and says nothing when it does not. The system $(1, 2, 3, 4)$ carries no chain — 3 does not divide 2 — but greedy is not wrong there either.

This distinction explains why this course never gives up the oracle. The sufficient condition removes the need for measurement on 13 of the 969 systems. For the remaining 956, the only source of information is the oracle; the condition not holding neither clears an approach nor condemns it. A testable condition comes before measurement, not instead of it.

The Second Corpus

The measurement moves beyond four-value systems: five-value systems over a wider range are generated with two seeds.

# Continuing from the previous blocks: Counter, greedy_coins, dp_coins come from there.
def generator(seed):
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def five_value_corpus(seed, n=40):
    """Five-value {1,a,b,c,d} systems; values between 2..40 and increasing."""
    r = generator(seed)
    items = []
    while len(items) < n:
        d = sorted({2 + r(39) for _ in range(4)})
        if len(d) == 4:
            items.append((1, *d))
    return items


for label, seed in (("first corpus (20260218)", 20260218),
                    ("second corpus (20260219)", 20260219)):
    systems = five_value_corpus(seed)
    broken, largest_diff = 0, 0
    for system in systems:
        s = Counter()
        bad = max((greedy_coins(system, t, s) - dp_coins(system, t, s))
                  for t in range(1, 61))
        if bad > 0:
            broken += 1
            largest_diff = max(largest_diff, bad)
    print(label, "| broken systems", broken, "/ 40 | ratio", round(broken / 40, 4),
          "| largest excess", largest_diff)

first corpus (20260218) | broken systems 39 / 40 | ratio 0.975 | largest excess 21
second corpus (20260219) | broken systems 40 / 40 | ratio 1.0 | largest excess 21

For five-value systems, the ratio is 0.9750 and 1.0000; the one-system difference between the two corpora is below the resolution. Adding more values does not fix greedy, it makes it worse — more values mean more ways to pay the remainder after taking the largest coin, and therefore more solutions greedy can miss. The largest excess also rises from 16 to 21.

This completes the contrast with K04’s three greedy procedures. There, the choice’s safety was proven, and the proof rested on a property of the input: the lightest edge crossing a cut, the two rarest symbols, non-negative edge weight. In a coin system, such a property depends on the system itself and is absent in most systems. Choosing the greedy approach means assuming that property exists; when the assumption is not written down, the procedure silently gives too much change.

Summary

• A greedy procedure takes whichever choice looks best at every step and never goes back; for it to be correct, the choice must be shown, by an exchange argument, to be present in one of the optimal solutions.
• The bottom-up solution was tested against brute force before being used in the broad sweep: 0 divergence on 100 inputs, brute force 13,584 steps, bottom-up 2785 steps.
• On four-value 827 of 969 systems, greedy gives too much change; the ratio is 0.8535 and the largest excess is 16 coins, at amounts 36 and 37 in the system $(1, 18, 19, 20)$.
• The source of the error is that taking the largest coin leaves a remainder that is expensive to pay back; greedy does not see that remainder at the moment of choice.
• Had the same sweep been done only up to 10, the number of broken systems would have been 85, not 827; the scope of testing determines the result, and saying “tested” means nothing without stating tested up to what.
• On five-value systems, the ratio rises to 0.9750 and 1.0000; adding values does not fix greedy, it carries the largest excess from 16 to 21.

Next Step

Greedy was wrong because it did not see the remainder. There is a cure for this: solve the remainder too, that is, compute and store the optimal solution of every subproblem. The bottom-up solution in this lesson already did this and was never wrong. The next lesson names that procedure and measures its two conditions — the overlapping of subproblems, and whether the optimal solution can be built from the optimal solutions of subproblems. It will show, with numbers, that when there is no overlap, storing gains nothing but still takes up space.