Greedy Choices

Lesson 10 of 11 · 7 min · Free, no account needed

What you will learn

A greedy algorithm takes the best-looking choice at each step and never looks back.
With coins 1, 5, 10, 25 greedy change is always best. With 1, 3, 4 it isn't: 6 = 3 + 3, not 4 + 1 + 1.
One counterexample is enough to prove that "always" is false.

Always grab the biggest coin first. Does that always give the fewest coins?
Pay 30 with as few coins as you can.
A robot follows that rule. Coins 1, 3 and 4. It must pay 6.
Step through its choices.
Beat the robot.
Pay 6 with coins 1, 3, 4 using fewer than 3 coins.
Greedy, and the counterexample.
A greedy algorithm takes the choice that looks best right now and never takes it back. It's fast and simple.
Sometimes greedy is always right (coins 1, 5, 10, 25). Sometimes it isn't (coins 1, 3, 4).
A counterexample is one case where a claim fails. Paying 6 with 1, 3, 4 is enough to prove "greedy always gives the fewest coins" false.
Write the robot.
For each coin, biggest first: while it fits, take it.
Which coin sets can fool the robot?
The robot tries every amount from 1 to 40. Sort the sets.
Counterexample hunter.
Coins 1, 7, 10. Find 3 amounts where the robot uses more coins than it needs.
Greedy on a map: always ride to the nearest town next.
Which route around all the towns is shorter? Tap it, then Check.
Nearest-next picks C, D, then E because they're close, and then must cross to far-away B and back. Visiting B before E avoids the long return.
Be the robot: pay 63 with 25, 10, 5 and 1.
Tap the coins in the order it takes them.
Design your own greedy trap.
A 1 plus two coins of your choice. Make the robot lose somewhere from 1 to 30.
Greedy fails when taking the biggest coin leaves a remainder that only many small coins can pay, while skipping it allows a tidier split.

Lessons are interactive and need JavaScript. Turn it on to play them.