Given a set of coins with different denominations and a value V, you want to find the least number of coins needed to represent the value V. Assume that there enough coins of any denomination available to you.
For example, for the coin set 1, 5, 10, 20 and V=6, we need two coins (5+1) and for V=19, we need at least six coins (10+5+1+1+1+1).
An intuitive algorithm uses the coin with the highest value for as long as possible and then continues with the next largest coin denomination smaller than the remaining value needed to be made up. Let’s call in the greedy coin changing algorithm. For V=19, this approach results in 10+5+1+1+1+1.
Does the “greedy” coin changing algorithm always use the least number of coins? It depends on the denominations given!
- For the US coins, this approach will always use the smallest number of coins.
- Consider the coin denominations 1, 3, 4, 5 and V=7. The greedy algorithm would use 3 coins (5+1+1) while the amount can be made up with 2 coins (3+4). Hence, there are denominations where the greedy algorithm does not use the smallest number of coins.
- Consider the coin denominations 1, 15, 25. Can you find an amount on which greedy does not use the minimum number of coins?
- Any existing currency will most likely have denominations for which the greedy algorithm provides the least number of coins.
Program: Algorithms_5_coinchanging.py
Note that the program assumes the denominations can make up the target value (which is always true when 1 is in the denominations). Adding code for testing this could be an exercise.
Discussion Topics
- A related problem is counting the total number of ways the target value v can be made up. This can be a big number! This is a combinatorial problem and a program written to count all possibilities is typically done with a recursive approach.
- Coin changing-like problems arise in other situations (e.g., making up postage, packing problems). There may be a limit on the number of times a “coin” can be used. The world is full of such optimization problems. Let your students come up with some, define and abstract them, and discuss possible algorithms solving them.
