Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



change problem
Posted:
Jul 19, 1996 10:20 PM


Hi I'm sure this problem has come up before but I'm not aware of any solution and was wondering if anybody out there knows of one.
Here is the problem: You have a bunch of coins and you have to give the coins out to people who need change. Also we know a solution exists. What is the fastest way to arrive at the solution. For example suppose you have 2 Quarters a dime and a 2 nickels and you have to make change for people who want 30 cents and 5 cents. You would give out the quarter and the nickel to person 1 and the other nickel to person 2. Assume I guess also you should only have exactly the right amount and kinds of coins, to get to a solution which of course could be one of many. Anybody know of an algorithm to do this? Thanks  Steve  something like solving a system of diophantine equations I guess which is NPcomplete???  I don't know. Watch that the algorithm is complete  it's trickier than you think.
Thanks Steve. 



