Knapsack: One constraint, each item can only be selected once, with a large number of items

Question

I'm writing an algorithm taking the knapsack problem form. I am trying to maximize the value (V) of my knapsack given a maximum weight (W). The catches are that each item (I) can only be selected once, the knapsack regardless of weight can only hold 10 items, and there is a very large number of items (500+).

My thoughts so far have been to generate a knapsack that is overweight and recursively work backwards replacing items one at a time until it is <= the max weight. This is not a problem for generating the most optimal knapsack, however, I would really like to generate the following 100 or so knapsacks. I was thinking I could do this by continuing my recursive process, however, I do not feel as though this is entirely accurate as a may be missing slightly more optimal knapsacks.

I do not care about minimizing weight, only maximizing value given the constraint of weight and ten items. The number of items must equal 10 and cannot be less than — mattbuell

David Eisenstat David Eisenstat · Accepted Answer · 2016-12-30T04:55:34

This problem can be formulated as an integer program.

maximize sum_{i in items} v_i * x_i
subject to
sum_{i in items} x_i <= 10       [u]
sum_{i in items} w_i * x_i <= W  [z]
for all i in items, x_i in {0, 1}  [y_i]

There are many solver libraries that will solve this program for you; alternatively, you can do the branch and bound yourself. Here's the dual linear program, which can be solved to obtain an upper bound on the objective value of the integer program, which is needed for branch and bound.

minimize 10 * u + W * z + sum_{i in items} y_i
subject to
for all i in items, u + w_i * z + y_i >= v_i  [x_i]
u >= 0
z >= 0
for all i in items, y_i >= 0

Given a value for z, setting the other variables is a matter of assigning positive y_i to the nine top items by v_i - w_i * z while assigning u to be the tenth greatest value. It should be possible to ternary search for z in time O(n log n).

Knapsack: One constraint, each item can only be selected once, with a large number of items

1 Answers