This problem is given on Project Euler here. In this post I'm going to show how to solve the Project Euler problem (using C#)..
From the link above:
Running a brute force algorithm on this would take forever, so instead we can try to devise a clever algorithm. First it might be helpful to imagine the problem if we didn't have so many coins. It's quite a pain to keep track of how many different coins there are when we try to think of a way to solve this problem. Instead we will solve a smaller problem by hand: how many ways are there to make 200p using only 1p and 2p coins?
This is a much easier problem. We can easily divide this into cases. There is as few as $0$ 2p pieces and as many as $100$. In any configuration if we knew how many 2p pieces there were then we would automatically know how many 1p pieces there were since the total value of the coins is 200p. Therefore, there are 101 ways to make 200p out of 1p and 2p pieces.
The 2 coin case was quite simple, so what if we add a third coin? How many ways can we make 200p using 1p, 2p and 5p pieces? We have an analog to the 2 coin case here. If we know how many 5p pieces we are using can we determine the number of ways to make the remaining change with only 1 and 2 pence pieces? To answer this critical question let's introduce the following notation.
$$p_k(n)=\text{the number of ways to make }n\text{ pence using coins of value }\leq{k}.$$
For example $p_1(n)=1$ for all $n$ because there is only one way to make any amount of change only using the 1p pieces.
How about $p_2(n)$? Here we can do casework. Above we solved a specific case ($p_2(200)$) by dividing into cases depending on how many $2p$ pieces we used. In general, $p_2(n)$ satisfies the recurrence $$p_2(n)=p_1(n)+p_1(n-2)+p_1(n-4)+...+p_1(n-2\lfloor{\frac{n}{2}}\rfloor)$$
The first term being the number of ways to make $n$ pence if we used no 2p pieces, the second term being the number of ways if we used 1, the third term if we used 2, etc. And the last term being if we used the maximum allowable number of 2p pieces. It's clear that there is nothing special about the fact we are using 2p pieces here and we could in fact make the same argument for 5p pieces and derive an expression of the form $$p_5(n)=p_2(n)+p_2(n-5)+p_2(n-10)+...+p_2(n-5\lfloor{\frac{n}{5}}\rfloor).$$
Here the skip from 5 to 2 is because there is no 3p piece and no 4p piece. This gives us an outline for an argument we can use for any coinage amount.
On your own you might try deriving the expression for 10p pieces and above.
All said and done here is an example of the code we might get solving this problem:
Now this solves the particular case from the Project Euler site. Running the code tells us the total number of ways to make $£2$ using the above coin combinations is $73,682$!
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) \text{ and } £2 (200p)$$
How many different ways can £2 be made using any number of coins?
This is a much easier problem. We can easily divide this into cases. There is as few as $0$ 2p pieces and as many as $100$. In any configuration if we knew how many 2p pieces there were then we would automatically know how many 1p pieces there were since the total value of the coins is 200p. Therefore, there are 101 ways to make 200p out of 1p and 2p pieces.
The 2 coin case was quite simple, so what if we add a third coin? How many ways can we make 200p using 1p, 2p and 5p pieces? We have an analog to the 2 coin case here. If we know how many 5p pieces we are using can we determine the number of ways to make the remaining change with only 1 and 2 pence pieces? To answer this critical question let's introduce the following notation.
$$p_k(n)=\text{the number of ways to make }n\text{ pence using coins of value }\leq{k}.$$
For example $p_1(n)=1$ for all $n$ because there is only one way to make any amount of change only using the 1p pieces.
How about $p_2(n)$? Here we can do casework. Above we solved a specific case ($p_2(200)$) by dividing into cases depending on how many $2p$ pieces we used. In general, $p_2(n)$ satisfies the recurrence $$p_2(n)=p_1(n)+p_1(n-2)+p_1(n-4)+...+p_1(n-2\lfloor{\frac{n}{2}}\rfloor)$$
The first term being the number of ways to make $n$ pence if we used no 2p pieces, the second term being the number of ways if we used 1, the third term if we used 2, etc. And the last term being if we used the maximum allowable number of 2p pieces. It's clear that there is nothing special about the fact we are using 2p pieces here and we could in fact make the same argument for 5p pieces and derive an expression of the form $$p_5(n)=p_2(n)+p_2(n-5)+p_2(n-10)+...+p_2(n-5\lfloor{\frac{n}{5}}\rfloor).$$
Here the skip from 5 to 2 is because there is no 3p piece and no 4p piece. This gives us an outline for an argument we can use for any coinage amount.
On your own you might try deriving the expression for 10p pieces and above.
All said and done here is an example of the code we might get solving this problem:
Cool Problem. Here's a recursive Python script for arbitrary n:
ReplyDeleteimport sys
def recursive(n,p,pc):
pic = pc - 1
if pic == 0:
return 1
else:
s = 0;
while n>=0:
s = s + recursive(n,p,pic)
print s
n = n - p[pic]
return s
# ------------------final output script --------------
n = int(sys.argv[1])
p = [1, 2, 5, 10, 20, 50, 100, 200]
final = recursive(n,p, len(p))
print final
I like it :). Good job on coming up with a solution! If you'd like to see another way to solve this problem (and many more interesting problems) check out this mathworld link. I'm thinking of doing a blog post on that as well, but it may be "too mathy."
ReplyDeletei think you can do this with generating functions as well.
ReplyDelete