Project Euler 31: Investigating combinations of English currency denominations
Project Euler 31 Problem Description
In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?
This is a typical problem that demonstrates the use of partitions which can be solved by using dynamic programming. To keep this problem simple: order does not matter, there are always enough coins to make a combination and we’re not looking for the optimal way to make change. This a perfect application for tested algorithms where this problem has been used as an example. As the details and nuances of dynamic programming are somewhat involved; we have provided some links below for a better explanation:
Coin Change – Algorithmist
Dynamic Programming Solution to the Coin Changing Problem
Project Euler 31 SolutionRuns < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 31 Solution Python 2.7 source.
AnswerSlowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
- See also, Project Euler 76 Solution: How many different ways can one hundred be written as a sum of at least two positive integers?
- This problem only wants the number of combinations. It would be a different approach if they wanted a set of combinations.