Greedy Strategies

Examples

A greedy algorithm builds a solution piece by piece and, at each step, chooses the most profitable piece. There are two natural implementations of this strategy: either iterative with a while loop or recursive. This is best illustrated with examples.

Largest Concatenate Problem

Our first example is the Largest Concatenate Problem: given a sequence of single-digit numbers, find the largest number that can be obtained by concatenating these numbers. For example, for the input sequence $(2,3,9,2,2)$, the output is the number $93222$. It is easy to come up with an algorithm for this problem. Clearly, the largest single-digit number should be selected as the first digit of the concatenate. Afterward, we face essentially the same problem: concatenate the remaining numbers to get as large a number as possible.

---

 $LargestConcatenate(Numbers)$:
 $result$ $\leftarrow$ empty string
 while $Numbers$ is not empty:
  $maxNumber$ $\leftarrow$ largest among $Numbers$
  append $maxNumber$ to $result$
  remove $maxNumber$ from $Numbers$
return $result$

---

Money Change Problem

Our second example is the Money Change Problem: given a non-negative integer $money$, find the minimum number of coins with denominations $1, 5,$ ...