Matching Sums Algorithm

[Aange10]

I'm not sure how to phrase a good subject, but to the point;

I've had a lot of fun at my job and chit chatting with my co-workers. But we always seem to get on the subject of what we want to do, inevitably leading me to describe some very elaborate albeit naive plans. In our discussion, we often talk about software development, and I decided I just wanted to make a little tool to take in a number (that our cash register is over) and look at all of the products we sell and see if we can match up an order to equal the amount we're over.

For instance if drinks are $3.50, popcorn is $2.20, a hot dog is $0.70, and our drawer is over $16.90, I'd like the program to deduce that we didn't ring up 1 drinks, 4 popcorn, and a hotdog.

Is there any easy way to do this? I realize across our menu there will be multiple combinations, so I'll probably show the top 10. But as far as computing the number, I was thinking about going through a for loop starting from highest priced to lowest, and if the price is below the total than to subtract it. For the equation earlier it'd look like this:

code:

3.50 < 16.90 -> True -> 16.90 - 3.50 = 13.40 3.50 < 13.40 -> True -> 13.40 - 3.50 = 9.90 3.50 < 9.90 -> True -> 9.90 - 3.50 = 6.40 3.50 < 4.40 -> True -> 6.40 - 3.50 = 2.90 3.50 < 2.90 -> False 2.20 < 2.90 -> True -> 2.90 - 2.20 = 70 0.70 < 0.70 -> True -> 0.70 - 0.70 = 0 return [ [4 popcorns, 1 drink, 1 hot dog], 0 cents off]

It's trivial if I could get that to work (by, say, noting i sold popcorn 4 times and looping back through and only selling it 3 times and moving to the next item to find more combinations), but if I can, I'd like to explore better options.

Thanks!

[DemonWasp]

You're looking at a variant of a very well-known problem in Computer Science: the Knapsack Problem. See: http://en.wikipedia.org/wiki/Knapsack_problem ; specifically, you have the unbounded knapsack problem.

The problem is one of the more difficult ones (in the computer science sense), though you're simplifying things by enforcing equality (=) rather than inequality (<=) and omitting the value-based optimization problem.

[Aange10]

Ahh, Thanks a ton DemonWasp! I'll get on working through that pseudo code