KP01

Solves the 0-1 knapsack problem using preprocessing and dynamic programming.

Description

[FMAX,X] = KP01(W,P,C) solves the combinatorial optimization problem

      maximize F = SUM(P.*X),
      subject to SUM(W.*X) <= C,

where the solution X is a binary vector of 0s and 1s. W and P are vectors
of weights and profits and C is the capacity of the knapsack. Weights must
be positive integers.

The knapsack solver uses preprocessing with estimation of lower and upper
bounds to reduce the problem to a core problem. The core problem is solved
by standard dynamic programming.

P = [] invokes the subset-sum solver. A subset-sum problem is the special
case P = W. The subset-sum solver uses preprocessing with small random
perturbations to reduce the problem size (if possible). The reduced problem
is solved by dynamic programming.

Acknowledgements

0 1 Knapsack inspired this file.

• MATLAB release: MATLAB 7.8 (R2009a)