# [C] 0/1 knapsack problem

There are n objects O_{1}, O_{2}, ..., O_{n} and a knapsack. Object O_{i} has weight w_{i} and value (price) p_{i}. Capacity of the knapsack is c units of weight. Solved by dynamic programming approach, M_{i,j} is denoted as maximal value that can be obtained my choosing objects from the set {O_{1}, O_{2}, ..., O_{i}} with the capacity j. When M_{i,j} is achieved, object O_{i} is either put in the knapsack or it is not. If O_{i} is not put in the knapsack, then M_{i,j} = M_{i-1,j}. If O_{i} is put in the knapsack, previously chooses object represents the optimal choice from the set {O_{1}, O_{2}, ...,O_{i-1}} with the capacity j - w_{i}.

The algorithm fills the matrix with values M_{i,j}. The value that is actually searched for is M_{n,c}. The matrix is formed with dimensions (n+1) * (c+1), and the order of computing is row by row (since j changes faster than i). Complexity is O(nc).

The table that should be formed by this algorithm, for values n = 3, (w_{1}, w_{2}, w_{3}) = (2,3,4), (p_{1}, p_{2}, p_{3)} = (1,7,8) and c = 6 looks like this:

\ j 0 1 2 3 4 5 6 i 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 2 0 0 1 7 7 8 8 3 0 0 1 7 8 8 9

That is, maximum value in the knapsack should be M_{3,6} = 9.

#### Source

Program successfully compiles under:

- [x86]gcc version 4.1.2 20061115 (prerelease) (Debian 4.1.1-21)
- [x86]Visual Studio 2008 Professional [Windows Vista x64]
- [IA64]gcc version 4.1.2 ia64-hp-hpux11.23