Computer Science Canada Making change with no '1' coin. |
| Author: | Insectoid [ Tue Feb 23, 2010 4:31 pm ] |
| Post subject: | Making change with no '1' coin. |
It's really not that hard to make a change-calculating program, but what if there is no penny? If, say, there are only nickles, dimes, and 4-cent coins (yea, I stole that example from wiki). What's the most efficient way to calculate this kind of change? I think a recursive solution would work, but is it efficient? I'm thinking along the lines of the following: 73 cents -> calculate max quarters (2) -> 23 cents -> calculate max dimes (2) -> 3 cents -> calculate max 4sies ->oh noes! impossible! V remove 1 dime (1) <------------------------------------------ back up to dimes V 13 cents -> calculate max 4sies -> 3, but we have 1 left over! And that's getting really illegible, so I'll describe it without crazy ascii-maps. Anyway, so it would back up to dimes again, drop another dime, calculate 4sies (5), find 4 left over, back up to dimes which backs up to quarters, drops a quarter, calculates dimes (4), then calculates 4sies (2) and then it's done. This seems pretty inefficient to me. Is there a faster way? |
|
| Author: | USEC_OFFICER [ Tue Feb 23, 2010 4:57 pm ] |
| Post subject: | RE:Making change with no \'1\' coin. |
Just have to point out a way to make it slightly faster: Odd numbers need an odd number of quarters. Even numbers an even amount. (Zero is even.) Thus any odd number that is below 29 can't be made with dimes and 4sies. |
|
| Author: | DemonWasp [ Tue Feb 23, 2010 5:04 pm ] |
| Post subject: | RE:Making change with no \'1\' coin. |
Note that it's actually impossible to make change in the second case, since 13 is odd and you have only one odd-valued coin, with value 25. You've noticed that what's called the Greedy Algorithm (the one most people use) doesn't work in this case, since it fails for 73. In general, the Greedy Algorithm should work for any valid number as long as the value of each successive coin is at most half of the value of the previous coin. My algorithms class (CS343 at UWaterloo) is actually going over this problem right now, looking at the "Dynamic Programming" style of algorithm design. The algorithm should be finished on Thursday; I'll update you then if I remember. |
|
| Author: | TheGuardian001 [ Tue Feb 23, 2010 5:29 pm ] |
| Post subject: | Re: RE:Making change with no \'1\' coin. |
DemonWasp @ Tue Feb 23, 2010 5:04 pm wrote: since 13 is odd and you have only one odd-valued coin, with value 25
When was the nickle removed? |
|
| Author: | DemonWasp [ Tue Feb 23, 2010 5:56 pm ] |
| Post subject: | RE:Making change with no \'1\' coin. |
He's using only three coins as an example problem (not necessarily Canadian currency), and they have values 25 cents, 10 cents, 4 cents. |
|
| Author: | jbking [ Wed Feb 24, 2010 10:37 am ] |
| Post subject: | Re: Making change with no '1' coin. |
While on the one hand it isn't hard to have various algorithms that can try to solve the problem, it can be interesting to look at part of this problem as an equation requiring positive integer co-efficients for a solution just to look at the Math side in terms of the existence of a solution. Thus, suppose there were just quarters, dimes and nickels to make change. It shouldn't be hard to see that there is a common factor of 5 in their values and thus any total that isn't divisible by 5 will require some form of rounding. Thus introducing other factors could be viewed as useful. However, this could be seen as being similar to the Knapsack problem though there is a Change-making problem page on Wikipedia too if you want other ideas for an answer. |
|
| Author: | USEC_OFFICER [ Wed Feb 24, 2010 12:46 pm ] |
| Post subject: | Re: Making change with no '1' coin. |
I was thinking about the change problem, and eventually came up with this. It seems to work fine. It works by elimating any odd numbers first, and then figuring out the number of 4ies needed. From there it is just quarters and dimes to figure out. Easy. |
|