Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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 NP-complete??? - I don't know.
Watch that the algorithm is complete - it's trickier than you think.
Thanks
Steve.
--
|
|
|
|
