GreedyGreedy

Greedy: When the Local Choice Is Safe

Build a solution by repeatedly taking the locally best choice — correct only when an exchange argument proves that choice never hurts.

Learn Greedy Algorithms →

Amount to make change for — The same amount is paid out twice: once with {25, 10, 5, 1} and once with {4, 3, 1}

taken

1/17Pay out 6 using the US coin denominations {1, 5, 10, 25}. The greedy rule never changes: repeatedly hand over the largest coin that still fits. Whether that rule is *correct* is a property of the coin system, not of the rule.

Denomination being consideredCoin just takenDenomination finishedToo large to fitWhere the optimal answer differs

PseudocodeLearn Greedy Algorithms →

1greedyChange(coins, target):          # coins sorted descending
2  taken = []
3  for d in coins:
4    while target >= d:                # take the biggest coin that fits
5      taken.append(d); target -= d
6  return taken
7# ground truth, for comparison — dynamic programming over every amount:
8  best[t] = 1 + min(best[t - d] for d in coins if d <= t)

Variables

system{1, 5, 10, 25}

remaining6

coinsUsed0

Complexity

best O(n)

avg O(n log n)

worst O(n log n)

space O(1)

Speed