Maximizing Knapsack with additional constraints

Question

The old and famous Knapsack problem requires that given a capacity C and a list of n items {I_1, I_2,..., I_n} with each I_j=(weight_j, value_j), one tries to maximize the value while filling up the knapsack.

But what happens if we add a constraint that

1) the number of times a specific item is chosen must either be 0 or must be odd (ex: can only take either no 10lb dumb-bells or 1, 3, 5,.. number of them). 2) C = n^2 and n <= weight_j <= n^2 for all j.

What implementation of dynamic programming can be used to handle the additional constraints?

Some advice would be greatly appreciated on how to begin. Thanks!

Answer 1

You can formulate this variation of the knapsack problem as an Integer Program

Standard Knapsack problem:

 Maximize sum(j) Value_j x X_j
 subject to
         sum(j) Wt_j x X_j <= C
         X_j is integer

In your variation, X_j can only take on distinct values: {0, 1,3,5,...}

Formulating the constraint to limit X to take on odd values

Whenever there are these types of restrictions on values a variable can take, introduce 0/1 variables to handle these conditions.

For each item j let's introduce a bunch of binary Y variables, and a couple of new constraints.

X_j - 1 Y_j1 - 3 Y_j3 - 5 Y_j5 ... - M Y_jm = 0 

m is the largest value (odd number) that Xj can take.

And to limit X_j to assume one of these values, we add

Y_j0 + Y_j1 + Y_j3 + ... + Y_jm = 1 for each item j
Y_j0, Y_j1, Y_j3 ..., Y_jm are {0,1} (binary)

The variable Y_j0 is to allow X_j to take on the value 0.

The fact that C = n^2 ensures that we can come up with reasonable upper limits m for each constraint.

You can now solve this modified knapsack with an integer programming solver. It will still look for the items in decreasing order of "value density" (value per kilo), while the constraints limiting it to odd values will kick in for certain boundary conditions.

Hope that helps.

Answer 2

The knapsack problem is an integer programming problem which in its simplest form can be solved via dynamic programming. Even seemingly small changes to the problem make it more difficult and much better suited for other approaches. The most straight-forward approach is to relax it to a number of linear programs while using the branch and bound to work your way through feasible solutions. Cutting planes can also be used - but people typically find it easier to understand and implement Branch and Bound. Take a look here http://mat.gsia.cmu.edu/orclass/integer/integer.html (simpler, more accessible) http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf (more complete)