2007-11-20

## The 0-1 Knapsack Problem

Posted by scvalexThe 0-1 Knapsack Problem (AKA The Discrete Knapsack Problem) is a famous problem solvable by dynamic-programming. In this article, I describe the problem, the most common algorithm used to solve it and then provide a sample implementation in C.

If you’ve never heard of the Knapsack Problems before, it will help to read this previous post.

#### The Problem

The Discrete (0-1) Knapsack Problem usually sounds like this:

Little Red Riding Hood wants to bring grandma a basket of goodies. She has an unlimited supply of

ntypes of sweets each weightingc[i]and having the nutritional value ofv[i]. Her basket can hold at mostWkilograms of sweets.Given

n,c,vandW, figure out which sweets and how many to take so that the nutritional value in maximal.

So, for this input:

`n = 3`

c = {8, 6, 4}

v = {16, 10, 7}

W = 10

LRRH should take one of *3* and one of *2*, amassing *17* nutritional points.

You’re usually dealling with a knapsack problem when you’re give the cost and the benefits of certain objects and asked to obtain the maximum benefit so that the sum of the costs is smaller than a given value. **You have got the Discrete Knapsack Problem** when you can only take **the whole object or none at all** and you have an **unlimited supply of objects**.

#### The Algorithm

This is a dynamic-programming algorithm.

The idea is to first calculate the maximum benefit for weight *x* and only after that to calculate the maximum benefit for *x+1*. So, on the whole, you first calculate the maximum benefit for *1*, then for *2*, then for *3*, …, then for *W-1* and, finally, for *W*. I store the maximum benefits in an array named *a*.

Start with *a[0] = 0*. Then for every *a* between *1 … W* use the formula:

`a[i] = max{v`

_{j} + a(i − c_{j}) | c_{j} ≤ i }

The basic idea is that to reach weight *x*, you have to add an object of weight *w* to a previous maximum benefit. More specifically, you have to add *w* to *x - w*. Now, there will probably be several ways to reach weight *x*, so you have to choose the one that maximises the benefit. That’s what the max is for.

Basically, the formula says: “To calculate the benefit of weight *x*, take every object (value: *v*; weight: *w*) and see if the benefit for *x - w* plus *v* is greater than the current benefit for *x*. If so, change it.”

So, for the example, the programme would output (and do) this:

`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.

#### The Programme

This programme runs in pseudo-plynominal time **O(n * W)**. i.e. Slow as hell for large very values of *W*. Also because it holds to arrays of at least length *W*, it’s also horribly memory inefficient. Unfortunately, there’s not much you can do.

Here’s the code in C (knapsack10.c):

#include <stdio.h> #define MAXWEIGHT 100 int n = 3; /* The number of objects */ int c[10] = {8, 6, 4}; /* c[i] is the *COST* of the ith object; i.e. what YOU PAY to take the object */ int v[10] = {16, 10, 7}; /* v[i] is the *VALUE* of the ith object; i.e. what YOU GET for taking the object */ int W = 10; /* The maximum weight you can take */ void fill_sack() { int a[MAXWEIGHT]; /* a[i] holds the maximum value that can be obtained using at most i weight */ int last_added[MAXWEIGHT]; /* I use this to calculate which object were added */ 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; }

That’s it. Good luck. Always open to comments.