The 0-1 Knapsack Problem

The 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 n types of sweets each weighting c[i] and having the nutritional value of v[i]. Her basket can hold at most W kilograms of sweets.

Given n, c, v and W, 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{vj + a(i − cj) | cj ≤ 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.