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.