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$.

---

Maximizing the value of the loot

Find the maximal value of items that fit into the backpack.

Input: The capacity of a backpack $W$, as well as the weights $(w_{1} ,\ldots,w_{n})$ and costs $(c_{1},\ldots, c_{n})$ of $n$ different compounds.

Output: The maximum total value of fractions of items that fit into the backpack of the given capacity, i.e., the maximum value of $c_{1}·f_{1}+\ldots+c_{n}·f_{n}$ ...