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?

Analysis

This is a typical problem that demonstrates the use of partitions which can be solved by dynamic programming. To keep this problem simple: order does not matter, there are always enough coins to make a combination and were 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

Solution

Runs < 1 second in Perl.

my $target = 200;
my @coins = (1,2,5,10,20,50,100,200);
my @ways = (1);
 
for $coin (@coins) {
  $ways[$_] += $ways[$_-$coin] for $coin..$target;
}
 
print "Answer to PE31 = $ways[$target]";

Comments

• See Problem 76. The advantage this code has is the problem only wants the number of combinations. It would be a different approach if they wanted a set of combinations.
• In Perl, the default variable, $_, takes the index value of the loop. In this case, values from $coin to $target.