Most efficient way to solve this combination problem

Question

I have 4 very large list (l1, l2, l3, l4) of components (approx 9 million items in each list). Each list item has a cost and a value.

I want to know how I can achieve the maximum combined value for an agreed combined total cost:

So, over all combinations in the 4 lists I want to know:

Max( l1[a].value + l2[b].value + l3[c].value + l4[d].value)

where

l1[a].cost + l2[b].cost + l3[c].cost + l4[d].cost <= X

X in the above is the total amount that I can spend.

I can obviously do this using a brute force method but that's going to take a long time to compute. I wondered if that was a more efficient way of doing this.

Any suggestions?

Answer 1

This is not the knapsack problem... But going through every possibility would take $O(n^4)$ time. This can be reduced to $O(n^3\log(n))$ by sorting the last list and going through every possible triple from the first 3 lists and finding by binary search the best object to take from the last list.

In practice you can probably prune off large parts of the search space by taking the 'best' object (with the highest value/cost ratio) from one list, then the best from another that can fit, until you have one from each list. This takes $O(n\log(n))$ time, and can be repeated for all $4!$ ways you can order the lists in the sequence. This will give a probably reasonably good bound on the optimal solution, and then you can run the above procedure but in each loop skipping all objects that make the total value necessarily less.