--- title: 'Greedy Algorithms' source: 'https://academia.sh/en/courses/advanced-algorithms/greedy-algorithms' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:26+00:00' license: 'CC BY-SA 4.0' --- # Greedy Algorithms Greedy choice is not a procedure until it is proven: on 827 of 969 four-value coin systems, greedy gives more coins than necessary, a ratio of 0.8535, with the largest excess being 16 coins; when the same error is tested only up to amount 10 instead of 50, it appears in just 85 of the systems. 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. ```python # 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. ```python # 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. ```python # 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. ```python # 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. ```python # 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.