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.
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:
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:
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:
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 6dollar notes. Therefore, there might be situations where it is better to choose a 6dollar note rather than a 20dollar 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?
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!
That's all for this tutorial! It's your turn to try some problems.
Greedy Algorithms 

