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


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
change problem
Replies:
1
Last Post:
Jul 21, 1996 8:21 PM




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. 



