Solving the best possible combination of 2 variables with a max limit

Hi there,

This is something I'm not sure is possible within excel but would be a huge help to my business. I thought of different ways it may be able to be done but couldn't come up with an answer. I wanted to ask the experts here to see what your thoughts are. I really appreciate the help and am glad to be on the forum.

My Problem

I am looking to solve for a set of data with 2 different variables to come up with the best possible combination. The 2 limitations are the number of data items I can choose as well as the maximum dollar value.

I would have 3 columns with multiple rows (100+)
The limitation is up to $100,000 without going over and 8 choices exactly no more or less
I would like to be able to solve what the best combination of 8 items are without going over my given dollar amount.

For Example


Item Value Cost
A 29 10,200
B 32 17,300
C 41 18,400
D 17 8000
E 28 21000
F 39 16,000
G 42 15,000
H 50 32,000
I 35 12,450
J 21 13,365
K 37 14,989
L 52 12,500
M 29 17,800
N 21 15300
O 36 14600
P 42 17500

Sorry thats not in a grid. But basis is letter / 2 digit number(value) / cost

What I would like to be able to do is to produce a formula that will give me the highest possible value from the value column based on having to choose exactly 8 items with a cost limit of 100,000

So basically what 8 items will give me the highest total value(no limit) with an upper cost limit of 100K that I can't go over?

If this is possible and someone can let me know how it can be done I would be very thankful. I can provide any further clarity needed.

Thanks In Advance,

slummer15

Also I am new to the forum and apologize if this isn't the correct place for this.

Hi slummer

I tried this in VBA using a 'brute force' approach, but it takes far too long to run (100^8/2 iterations - 10 million billion, I think.) My 3 year old laptop is estimating around 8000 years at present.

I have done some more research. This is a maths problem known as the 0-1 knapsack problem (Wiki describes it here http://en.wikipedia.org/wiki/Knapsack_problem)

If I am reading Wiki correctly, this problem is pseudo-polynomial, which means that it is essentially a brute force problem. However, there may be short cuts to speed things up. In the Wiki, there is discussions of comparison of subsets and binary searches. Also, you want exactly 8 items, a constraint not discussed therein.

I know it is possible using VBA, if you have a fast enough computer, or a lot of time. However, the maths to reduce this time to practical terms is beyond me.

In summary, I think the programming is a little complicated (I'm not the gods' gift to programming), and the maths is more than I can deal with (I do have an engineering degree, so my maths isn't that bad).

I don't know if any of this has been of use. Do you have any good mathematicians in your organisation?

Cheers, Rob.

Thanks Rob,

I appreciate the response. I'm going to look into this. I guess conceptually i didn't think it was a hard concept but I when i put it down or tried to do it I just couldn't seem to figure it out. I'm going to look into trying in VBA more but like you said the combinations could be endless. If anyone else has an idea for this I would love to hear it.

Thanks

slummer