Excel math puzzle

December 14, 2010 8:50 AM

Excel question. Is there a way to determine a list of all possible values from a list that add up to a given total?

Sort of like the math puzzle "I have 26 coins in my pocket totaling 17 dollars, how many of each coin are there?" Our stupid, outdated Point-Of-Sale system has some serious shortcomings, one of which is no remittance advice on statements. So it becomes a chore for our bookkeeper, when he receives a check for $231.68 to try to figure out which combination of invoices on an account totals up to that amount. It's mostly trial and error.

Is there a way to set up a spreadsheet where you could enter a series of dollar amounts down a column, and then enter a remittance amount in another cell, and then have it calculate which combination of those dollar amounts adds up to the remittance amount?

My level of Excel macro experience is probably medium; I have developed several sheets with deeply nested if/then statements pulling data from several sheets etc. But I have no idea where to start with something like this. :(

posted by xedrik to computers & internet (4 answers total)

Sounds like the knapsack problem to me, which was previously discussed here on AskMe.

Googling reveals this code, which finds a solution, but I have not tested, tried or even really looked at it.
posted by Jugwine at 8:57 AM on December 14, 2010

Oh, wow. I really did search but somehow missed that thread. "Knapsack Problem" helps a lot; I didn't know what the common name for that scenario is. Thanks much, that gives me a lot to investigate! (^.^)d
posted by xedrik at 9:00 AM on December 14, 2010

Obligatory XKCD.
posted by Cogito at 12:48 PM on December 14, 2010 [1 favorite]

The Knapsack Problem is the problem of finding the best solution to the puzzle, surely? Where there are multiple answers?

That doesn't appear to be your problem. You want to find the actual combinations which added up to the total. But there exist multiple solutions. How can your bookkeeper, doing it by trial and error, know they've got it right?
posted by AmbroseChapel at 4:53 PM on December 15, 2010