Question 97927
Hi,<br />

This is actually solved by using a technique called Dynamic Programming. Many students (including myself a few years ago) feared dynamic programming because it makes your head hurt a lot. I've never seen it taught to anyone below degree level, but here goes:<br />

Imagine you only have one coin, and let that coin have value c1. There are only two values you can make, right? You can either not use that coin and have $0, or you can use that coin and have $c1.<br />

If we now imagine two coins, the same one as before with value c1, and another with value c2 (c1 might equal c2, it doesn't matter). What happens is for each value we can make with the first coin (0, and c1) we can choose to add the value of c2 to it (use the second coin) or add nothing to it. This gives us totals of:<br />

0: make a total of 0 with the first coin, and then don't use this one.
c2: make a total of 0 with first coin and then use this one
c1: make a total of c1 with first coin and don't use this coin
c1+c2: make a total of c1 with first coin and use this coin.<br />

Now, the really cool thing is that this idea generalises to n coins. If we can make totals t1, t2, t3, t4, ... with n coins, then the totals that we can make with n+1 coins are all the totals we can make with n coins (don't use the (n+1)th coin) or the value of the (n+1)th coin plus all the totals we can make with n coins.<br />

For example, if with 3 coins we can make the totals 1,2,5,8,9 and we have a coin worth 4, then the totals we can make are 1,2,5(can make this 2 ways),6,8,9(can make this 2 ways),12,13. Make sure you understand where these numbers come from and can get them yourself.<br />

Well, that's the basic idea so let's try it on your problem. The coins we have are 25,25,25,10,10,5,1,1.<br />

So starting with the first coin we can either use it or not. That gives us 0 and 25.<br />

With the second coin we can make 0, 25(two different ways), 50.<br />

Third coin: 0, 25, 50, 75.<br />

Fourth coin: 0, 10, 25, 35, 50, 60, 75, 85<br />

Fifth coin: 0, 10, 20, 25, 35, 45, 50, 60, 70, 75, 85, 95<br />

Sixth coin: 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 85, 90, 95, 100<br />

Seventh coin: 0, 1, 5, 6, 10, 11, 15, 16, 20, 21, 25, 26, 30, 31, 35, 36, 40, 41, 45, 46, 50, 51, 55, 56, 60, 61, 65, 66, 70, 71, 75, 76, 85, 86, 90, 91, 95, 96, 100, 101<br />

I'll leave you do do the final coin, and then count how many different numbers you have.<br />

***I could quite well have accidently made a mistake in my working, so do check through it all and make sure you agree with my numbers - if not post what you disagree with and I'll get my computer to check it.***<br />

Kev