Greedy Algorithms

Greedy algorithms are a common type of algorithm seen in informatics solutions. Let's jump right in with an example: Fashion Statement from AIO 2006. In this problem, you need to carry exactly t dollars using the fewest notes possible. There are 4 denominations of notes available to you: 1, 5, 20, and 100 dollars. You have an unlimited supply of each.

Spend some time thinking about how to solve this problem. Then, click to reveal my solution idea.

Solution Idea

Intuitively, it is better to use bigger notes rather than smaller notes. This inspires a solution: We choose one note at a time, always choosing the biggest possible note.

For example, if we need t = 167 dollars, then we would do the following:

  • Choose a 100-dollar note. We now need 67 more dollars.
  • Choose a 20-dollar note. We now need 47 more dollars.
  • Choose a 20-dollar note. We now need 27 more dollars.
  • Choose a 20-dollar note. We now need 7 more dollars.
  • Choose a 5-dollar note. We now need 2 more dollars.
  • Choose a 1-dollar note. We now need 1 more dollar.
  • Choose a 1-dollar note. We now have 167 dollars, and are finished.
This uses 7 notes.

This algorithm has a time complexity of \(O(t)\), which is fast enough to score all 100 points on this problem. In code, this might look like:

answer = 0
while t > 0:
    if t >= 100:
        t -= 100
        answer += 1
    elif t >= 20:
        t -= 20
        answer += 1
    elif t >= 5:
        t -= 5
        answer += 1
    else:
        t -= 1
        answer += 1
int answer = 0;
while (t > 0) {
    if (t >= 100) {
        t -= 100;
        answer += 1;
    } else if (t >= 20) {
        t -= 20;
        answer += 1;
    } else if (t >= 5) {
        t -= 5;
        answer += 1;
    } else {
      t -= 1;
      answer += 1;
    }
}

My solution is called a greedy algorithm because it tries to make the best choice at each step, without thinking about future choices. But how do we know whether this algorithm always uses the fewest number of notes? To convince ourselves, we either need a proof that it works, or a proof that it doesn't work:

Try to prove or disprove my solution, and then click to reveal my reasoning.

Is the solution correct?

The solution is correct! To prove this, we need to understand why it is always better to take a higher valued note over a lower valued note:

  • If we had five 20-dollar notes, it is always better to replace these with a single 100-dollar note, since both options have the same value but the second option uses fewer notes.
  • If we had four 5-dollar notes, it is always better to replace these with a single 20-dollar note, using the exact same reasoning as above.
  • If we had five 1-dollar notes, it is always better to replace these with a single 5-dollar note, using the exact same reasoning as above.
Therefore, it is always best to take the biggest note possible, and so the solution is correct.

Another Example

Our next example is the same problem as before, except you now have the following notes available to you: 1, 6, 20, and 100 dollars. Notably, the 5 dollar note has been replaced by a 6 dollar note. Does our previous solution work? Have a think about it, and then click to see whether you are correct.

Does the solution work on this version of the problem?

No! Many problems cannot be solved using a greedy algorithm, and this is one of them. Our old proof does not work because you cannot make 20 using just 6-dollar notes. Therefore, there might be situations where it is better to choose a 6-dollar note rather than a 20-dollar note.

To prove that the greedy solution is incorrect, we can make a test case where the greedy solution uses too many notes. Can you find one?

Breaking Case

Try t = 24. The greedy algorithm uses 5 notes: 20+1+1+1+1. However, we can actually make 24 using only 4 notes: 6+6+6+6.

A common mistake for newer students is using greedy algorithms when they don't work, causing them to score 0 points. To avoid this happening to you, always be careful when using a greedy algorithm!

Exercises

That's all for this tutorial! It's your turn to try some problems.

Greedy Algorithms

Click here to go back.