Introduction to Greedy Algorithms

Greedy algorithms

In this chapter, we’ll learn about seemingly naive yet powerful greedy algorithms. After learning the key idea behind the greedy algorithms, some students feel that they represent the algorithmic Swiss Army knife that can be applied to solve nearly all programming challenges in this course. Be warned: since this intuitive idea rarely works in practice, we have to prove that our greedy algorithm produces an optimal solution!

We’ll be solving the following problems with greedy algorithms:

---

Money change

Compute the minimum number of coins needed to change the given value into coins with denominations $1$, $5$, and $10$.

Input: An integer $money$.

Output: The minimum number of coins with denominations $1$, $5$, and $10$ that changes $money$.