Yet another excel question!

November 4, 2008 2:49 PM

I have an Excel question that I'm not sure how to search the archives for.

Apologies if this has been asked/answered before, but I'm not sure how to phrase the search I tried, so I'll ask here again. If I have a list of a whole lot of unique numbers, is there an Excel function or SIMPLE VB statement (I am by no means a guru with VB - it rather terrifies me) that can tell me if any combination of numbers in my list add up to a target value in another cell? For instance, if I have the following in cells A1-A6:

1
2
3
12
97
450.6

and in cell C1 I have 455.6, can I make Excel tell me (via highlighting, or via a Y/N flag in an adjacent column, or something) that the values in my Column A list that add up to the value in C1 are in A2, A3, and A6?

posted by pdb to computers & internet (4 comments total)

This requires programming. It's typically referred to as the knapsack problem. There is no simple VB function that isn't basically an implementation of some solution to the knapsack problem, any of which I would characterize as non-simple relative to Excel.
posted by GuyZero at 2:55 PM on November 4, 2008

Actually, it's simpler than wikipedia's description of the knapsack problem, but it's still a non-trivial optimization exercise. You essentially have to check all 2^n combination of n items to see which ones meet the criteria. You could do it in a single loop now that I think about it (sorry to jump the gun a bit there) but I do not have such a fragment of VB code handy (and I am pretty bad with VB)
posted by GuyZero at 2:59 PM on November 4, 2008

Here is a link to the Microsoft Excel discussion forum. I've always been able to get answers to my Excel questions there - especially when VB is making me want to rip my eyes out.
posted by youngergirl44 at 5:51 PM on November 4, 2008

No, you were right initially. This is a variant of the knapsack problem called the 0-1 knapsack problem, which is discussed in the Wikipedia article. (Actually the 0-1 knapsack doesn't require unique numbers, which is posed in the question, but I doubt that this changes the nature of the problem.) This is a difficult problem that would require VBA to solve.
posted by zixyer at 6:07 PM on November 4, 2008