Question 97927This question is from textbook prentice Hall Pre- Algebra
: I really need help wih this, I have no idea where to begin to figure this out??? Please Show me the steps. Thanks for your time and all efforts put forht to answer this problem for me>>...
Jayne has 3 quarters, 2 dimes, a nickel and 2 pennies in her pocket. How many different amounts of money can she make using some or all of her change?
Thank you, Thank You, THANK YOU!!!
This question is from textbook prentice Hall Pre- Algebra
Answer by kev82(151)   (Show Source):
You can put this solution on YOUR website! Hi,
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:
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.
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:
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.
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.
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.
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.
So starting with the first coin we can either use it or not. That gives us 0 and 25.
With the second coin we can make 0, 25(two different ways), 50.
Third coin: 0, 25, 50, 75.
Fourth coin: 0, 10, 25, 35, 50, 60, 75, 85
Fifth coin: 0, 10, 20, 25, 35, 45, 50, 60, 70, 75, 85, 95
Sixth coin: 0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 85, 90, 95, 100
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
I'll leave you do do the final coin, and then count how many different numbers you have.
***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.***
Kev
|
|
|
