0/1 Knapsack Problem

OBJECTIVE: Implementation of 0-1 dynamic knapsack problem.
THEORY: Let i be the highest-numbered item in an optimal solution S for W pounds. Then S` = S - {i} is an optimal solution for W - wi pounds and the value to the solution S is Vi plus the value of the subproblem.

We can express this fact in the following formula: define c[i, w] to be the solution for items  1,2, . . . , i and maximum weight w. Then
             0            if i = 0 or w = 0
c[i,w]  = c[i-1, w] if wi ≥ 0
  max [vi + c[i-1, w-wi], c[i-1, w]} if i>0 and w ≥  wi
The algorithm takes as input the maximum weight W, the number of items n, and the two sequences v = <v1, v2, . . . , vn> and w = <w1, w2, . . . , wn>. It stores the c[i, j] values in the table, that is, a two dimensional array, c[0 . . n, 0 . . w] whose entries are computed in a row-major order. That is, the first row of c is filled in from left to right, then the second row, and so on. At the end of the computation, c[n, w] contains the maximum value that can be picked into the knapsack.
PROGRAM:
#include <stdio.h>
#define MAXWEIGHT 100
int n = 3;
int c[10] = {8, 6, 4};
int v[10] = {16, 10, 7};
int W = 10;
void fill_sack() {
int a[MAXWEIGHT];
int last_added[MAXWEIGHT];
int i, j;
int aux;
for (i = 0; i <= W; ++i) {
a[i] = 0;
last_added[i] = -1;
}
a[0] = 0;
for (i = 1; i <= W; ++i)
for (j = 0; j < n; ++j)
if ((c[j] <= i) && (a[i] < a[i - c[j]] + v[j])) {
a[i] = a[i - c[j]] + v[j];
last_added[i] = j;
}
for (i = 0; i <= W; ++i)
if (last_added[i] != -1)
printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n", i, a[i], last_added[i] + 1, v[last_added[i]], c[last_added[i]], i - c[last_added[i]]);
else
printf("Weight %d; Benefit: 0; Can't reach this exact weight.\n", i);
printf("---\n");
aux = W;
while ((aux > 0) && (last_added[aux] != -1)) {
printf("Added object %d (%d$ %dKg). Space left: %d\n", last_added[aux] + 1, v[last_added[aux]], c[last_added[aux]], aux - c[last_added[aux]]);
aux -= c[last_added[aux]];
}
printf("Total value added: %d$\n", a[W]);
}
int main(int argc, char *argv[]) {
fill_sack();
return 0;
}
OUTPUT:
Weight 0; Benefit: 0; Can't reach this exact weight.
Weight 1; Benefit: 0; Can't reach this exact weight.
Weight 2; Benefit: 0; Can't reach this exact weight.
Weight 3; Benefit: 0; Can't reach this exact weight.
Weight 4; Benefit: 7; To reach this weight I added object 3 (7$ 4Kg) to weight 0
Weight 5; Benefit: 7; To reach this weight I added object 3 (7$ 4Kg) to weight 1
Weight 6; Benefit: 10; To reach this weight I added object 2 (10$ 6Kg) to weight 0
Weight 7; Benefit: 10; To reach this weight I added object 2 (10$ 6Kg) to weight 1
Weight 8; Benefit: 16; To reach this weight I added object 1 (16$ 8Kg) to weight 0
Weight 9; Benefit: 16; To reach this weight I added object 1 (16$ 8Kg) to weight 1
Weight 10; Benefit: 17; To reach this weight I added object 2 (10$ 6Kg) to weight 4
---
Added object 2 (10$ 6Kg). Space left: 4
Added object 3 (7$ 4Kg). Space left: 0
Total value added: 17$