[C] 0/1 knapsack problem

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

The algorithm fills the matrix with values Mi,j. The value that is actually searched for is Mn,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, (w1, w2, w3) = (2,3,4), (p1, p2, p3) = (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 M3,6 = 9.

Source

0-1_knapsack.c

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