The change making problem has become something of a classic due to what it can show us about different approaches to algorithmic problem solving.
In this article we will look at the greedy approach using Python. A greedy algorithm is one which makes locally optimal choices at any given point, and once a choice is made, does not revisit it. This can make the algorithm “short-sighted”, and it may not find the optimal solution. However, there are advantages to the greedy approach.
Greedy Algorithms Features
- Makes locally optimal choices
- Does not revisit choices once made
Greedy Algorithms Advantages
- Often quite fast
- Relatively easy to implement
Greedy Algorithms Disadvantages
- “Short-sighted”. May not provide optimal solution
- May fail on some instances of a problem
The change-making problem involves finding the minimum number of coins from a set of denominations that add up to a given amount of money. For example, say you have coins available of denominations
1p, 2p, 5p, 10p, 20p, 50p, £1 and
£2 , as in the UK.
What is the minimum number of coins you need to make
5: £1 + 50p + 10p + 2p + 1p
Have a go at implementing a solution to this problem for yourself in Python, then check out my solution below. Here’s some boilerplate to get you started:
def make_change(target_amount): pass # Write your solution here. print(make_change(163))
And here is my solution:
def make_change(target_amount): denominations = [200, 100, 50, 20, 10, 5, 2, 1] # Order is important! coin_count = 0 # Initialise count count values =  # Store values here for coin in denominations: while target_amount >= coin: # Use the current coin until its value is too large target_amount -= coin # Decrease the remaining amount values.append(coin) # Make a note of which coin was used coin_count += 1 # Increase the coin count return coin_count, values print(make_change(163)) Output: (5, [100, 50, 10, 2, 1])
This version keeps track of which coins are used, which isn’t always necessary if you just want the minimum number of coins.
With UK coins, and many other sets, this algorithm actually gives the optimal solution. This is not always the case, however, and with some combinations of available denominations, the greedy algorithm fails. For example, if you only had coins of denominations
3p, and wanted to make
4p, the algorithm would select
3p first, then have no way to make the required value of
One thing that makes the change making problem interesting is that it can be solved in other ways which avoid some of the pitfalls of the greedy approach. For example, it can be solved using dynamic programming, which I will cover in a future article.
This article has discussed what greedy algorithms are, and shown an example in Python for solving the change making problem. I hope you found it interesting and helpful. Happy computing!