Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

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

 Messages: [ Previous | Next ]
 Steve Kettle Posts: 6 Registered: 12/12/04
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 NP-complete??? - I don't know.
Watch that the algorithm is complete - it's trickier than you think.

Thanks
Steve.
--

Date Subject Author
7/19/96 Steve Kettle
7/21/96 Ilias Kastanas