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 24p?

  or £1.63?

  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 2p and 3p, and wanted to make 4p, the algorithm would select 3p first, then have no way to make the required value of 4p.

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!

Sharing is caring!