Giving change with the fewest notes
A shopkeeper's program gives change in Nepali notes and coins. Run it for different amounts and watch the greedy rule at work: always give the largest note that still fits. Count the notes, and find out when being greedy is not the best plan.
Core concept
A greedy algorithm makes the best-looking choice at each step: for change, it gives the largest note that still fits, again and again, until nothing is left
Topic: Algorithms
When a shopkeeper gives you change, they do not try every mix of notes. They start with the biggest note that is not too big, give as many of it as fit, then move to the next smaller note, until nothing is left. This is called a greedy algorithm: A list of clear steps that solves a problem, like a recipe. All key words: at every step it takes the choice that looks best right now. In a program each note becomes a WHILE loop: Steps that repeat, either a set number of times or until something becomes true. All key words: WHILE what is left is at least 100, give a 100 note and take 100 away. With Nepali notes and coins (500, 100, 50, 20, 10, 5 and 1 rupees) the greedy way always gives the fewest notes. But for some unusual sets of coins the greedy choice is not the best one, so programmers must check that a greedy rule really works.
What you will learn
- Explain the greedy rule for giving change.
- Trace a sequence of WHILE loops that each give one kind of note.
- Count the notes the program gives for an amount.
- Give an example where a greedy choice is not the best.
Before you start
- Know how a WHILE loop repeats while its condition is true.
Materials
- A notebook to write the notes for each amount
Equipment
- None
Procedure
- Run the program for Rs 375 and count the notes it gives.
- Step through it once and watch what is left after each note.
- Try Rs 1000 and Rs 85.
- Answer the practice challenges.