Problems


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&#91;i&#93; = 0;
		last_added&#91;i&#93; = -1;
	}

	a&#91;0&#93; = 0;
	for (i = 1; i <= W; ++i)
		for (j = 0; j < n; ++j)
			if ((c&#91;j&#93; <= i) && (a&#91;i&#93; < a&#91;i - c&#91;j&#93;&#93; + v&#91;j&#93;)) {
				a&#91;i&#93; = a&#91;i - c&#91;j&#93;&#93; + v&#91;j&#93;;
				last_added&#91;i&#93; = j;
			}

	for (i = 0; i <= W; ++i)
		if (last_added&#91;i&#93; != -1)
			printf("Weight %d; Benefit: %d; To reach this weight I added object %d (%d$ %dKg) to weight %d.\n", i, a&#91;i&#93;, last_added&#91;i&#93; + 1, v&#91;last_added&#91;i&#93;&#93;, c&#91;last_added&#91;i&#93;&#93;, i - c&#91;last_added&#91;i&#93;&#93;);
		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.

Advertisements

In this article, I describe the greedy algorithm for solving the Fractional Knapsack Problem and give an implementation in C.

The Problem

The Fractional Knapsack Problem usually sounds like this:

Ted Thief has just broken into the Fort Knox! He sees himself in a room with n piles of gold dust. Because the each pile has a different purity, each pile also has a different value (v[i]) and a different weight (c[i]). Ted has a knapsack that can only hold W kilograms.

Given n, v, c and W, calculate which piles Ted should completely put into his knapsack and which he should put only a fraction of.

So, for this input:
n = 5
c = {12, 1, 2, 1, 4}
v = {4, 2, 2, 1, 10}
W = 15

Ted should take piles 2, 3, 4 and 5 completely and about 58% of pile 1.

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’ve got the fractional knapsack problem when you can take fractions (as opposed to all or nothing) of the objects.

The Algorithm

This is a standard greedy algorithm. In fact, it’s one of the classic examples.

The idea is to calculate for each object the ratio of value/cost, and sort them according to this ratio. Then you take the objects with the highest ratios and add them until you can’t add the next object as whole. Finally add as much as you can of the next object.

So, for our example:
v = {4, 2, 2, 1, 10}
c = {12, 1, 2, 1, 4}
r = {1/3, 2, 1, 1, 5/2}

From this it’s obvious that you should add the objects: 5, 2, 3, 4 and then as much as possible of 1.
The output of my programme is this:
Added object 5 (10$, 4Kg) completly in the bag. Space left: 11.
Added object 2 (2$, 1Kg) completly in the bag. Space left: 10.
Added object 3 (2$, 2Kg) completly in the bag. Space left: 8.
Added object 4 (1$, 1Kg) completly in the bag. Space left: 7.
Added 58% (4$, 12Kg) of object 1 in the bag.
Filled the bag with objects worth 15.48$.

The Programme

Now, you could implement the algorithm as stated, but for practical reasons you may wish to trade speed for simplicity. That’s what I’ve done here: instead of sorting the objects, I simply go through them every time searching for the best ratio. This modification turns an O(n*lg(n)) algorithm into an O(n2) one. For small values of n, this doesn’t matter and n is usually small.

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

#include <stdio.h>

int n = 5; /* The number of objects */
int c[10] = {12, 1, 2, 1, 4}; /* c[i] is the *COST* of the ith object; i.e. what
				YOU PAY to take the object */
int v[10] = {4, 2, 2, 1, 10}; /* v[i] is the *VALUE* of the ith object; i.e.
				what YOU GET for taking the object */
int W = 15; /* The maximum weight you can take */

void simple_fill() {
	int cur_w;
	float tot_v;
	int i, maxi;
	int used[10];

	for (i = 0; i < n; ++i)
		used&#91;i&#93; = 0; /* I have not used the ith object yet */

	cur_w = W;
	while (cur_w > 0) { /* while there's still room*/
		/* Find the best object */
		maxi = -1;
		for (i = 0; i < n; ++i)
			if ((used&#91;i&#93; == 0) &&
				((maxi == -1) || ((float)v&#91;i&#93;/c&#91;i&#93; > (float)v[maxi]/c[maxi])))
				maxi = i;

		used[maxi] = 1; /* mark the maxi-th object as used */
		cur_w -= c[maxi]; /* with the object in the bag, I can carry less */
		tot_v += v[maxi];
		if (cur_w >= 0)
			printf("Added object %d (%d$, %dKg) completly in the bag. Space left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w);
		else {
			printf("Added %d%% (%d$, %dKg) of object %d in the bag.\n", (int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1);
			tot_v -= v[maxi];
			tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];
		}
	}

	printf("Filled the bag with objects worth %.2f$.\n", tot_v);
}

int main(int argc, char *argv[]) {
	simple_fill();

	return 0;
}

That’s it. Good luck.

Always open to comments.

Update: The next article in this series is The 0-1 Knapsack Problem.

Checker Challenge is a very famous programming problem. It’s one of the first examples of backtracking anyone learns and variations of it frequently appare in contests.

In this article, I’ll present the classic algorithm for solving it and then a few optimisations to make it run less like a geriatric turtle.

First the problem:

Given a checker table of n lines and n columns, find all the ways of placing n checker pieces so that no two are on the same line, column or diagonal.

If n is greater or equal to 6 there is always at least one way to arrange the pieces. Usually there are a lot of ways (there are 73712 for n = 13).

For n = 6, this is one of the possible four arrangements:

| | O | | | | |
| | | | O | | |
| | | | | | O |
| O | | | | | |
| | | O | | | |
| | | | | O | |

First of all, you need a way to memorise the board. A matrix of n x n is the obvious solution, but it’s not really necessary. Notice that there can be at most one piece on any column, so it’s enough to use an array of n, each element containing the number of the row on which the corresponding element in the matrix is located. e.g. For the board above, the array would be {4, 1, 5, 2, 6, 3}.

Now, how do you approach such a problem? The simplest way (and, as it happens, the fastest) is to solve it recursively: first take the first column and attempt to place a piece on each of the n rows; for each of these, attempt to place a piece on each row of the second column; for every valid such arrangement, try to place a piece on each row of the third column; …; and so on until you place a piece on the nth column, at which point, you have a valid arrangement.

The key point in this algorithm is to know that when you’re working on the kth column, all the pieces on the first k – 1 columns form a valid arrangement.

As it happens, this is way to slow. For n = 10, I got tired of waiting and stopped the programme. If you do the math, you’ll see that for n, this algorithm does about nn recursive calls. This is bad, but if you write the checking routines inefficiently, you can easily make it slower by a factor of n.

There are three ways I know of to check if a position is valid (i.e. if a piece can be placed there). The first checks for validity after the piece has been placed, while the other two work by marking positions as invalid:

  1. The first is simple: let’s say you’ve reached column c and are wondering whether or not you can place a piece of row r. First take all the columns before c and check whether a piece is already on row r; afterwards, for every column c’ before c, and for every row r’ on that column check if abs(r – r’) = c – c’. If any of there conditions are true, than you can’t place a piece on row r.
  2. The second is just a way of trading memory for speed. Instead of doing as above, keep three vectors of boolean values (1 for the lines (usedRows) and 2 for the two types of diagonals (d1 and d2)), and for every piece you place on the board mark the corresponding elements in the three vectors as used. That is, mark rth element in rows, the n – c – 1 + r th element in d1 and the r + c th element in d2. If any of the corresponding elements for any position are marked, than that position is invalid.
  3. The third way is just combining the first two. For every row column c’ before c, supposing the piece is on row r’, mark the rows r’, r’ – (c – c’) and r’ + (c – c’) as invalid.

That’s it. For another speed boost, I use bitsets instead of vectors. Anyway, here’s the code in C (checker.c):

#include <stdio.h>
#include <string.h>

int q[14];

int sol[3][14];

int r = 0,
	d1 = 0,
	d2 = 0;

int solP = 0;

int n;

void gen_sol(int col) {
	if (col == n) {
		if (solP < 3)
			memcpy(sol&#91;solP&#93;, q, sizeof(int) * n);
		++solP;
		return;
	}

//NOTE Just calculating the non-admisible rows for this col every time is slightly faster than the "keep track of used rows and diagonals" solution
// 	int oc = 0;
// 	for (int i(0); i < col; ++i) {
// 		oc |= 1<<q&#91;i&#93;;
// 		oc |= 1<<(q&#91;i&#93; - (col - i));
// 		oc |= 1<<(q&#91;i&#93; + (col - i));
// 	}


	int i;
	for (i = 0; i < n; ++i) {
		if (!(r & 1<<i) && !(d1 & 1<<(n - col - 1 + i)) && !(d2 & 1<<(i + col))) {
			r |= 1<<i;
			d1 |= 1<<(n - col - 1 + i);
			d2 |= 1<<(i + col);
			
			q&#91;col&#93; = i;
			gen_sol(col + 1);

			r ^= 1<<i;
			d1 ^= 1<<(n - col - 1 + i);
			d2 ^= 1<<(i + col);
		}
	}
}

int main(int argc, char *argv&#91;&#93;) {
	n = 6;

	// Every solution's reflection is also a valid solution, so for the first
	// calculate only the first n/2 arrangements.
	int max = n;
	if (6 != n) {
		max = (n + 1) / 2;
	}
	
	// This complication appears because the odd values of n. Think about
	// it for a while and it will become obvious.
	int temp;
	int i;
	for (i = 0; i < max; ++i) {
		temp = solP;

		r |= 1<<i;
		d1 |= 1<<(n - 1 + i);
		d2 |= 1<<(i);

		q&#91;0&#93; = i;
		gen_sol(1);

		r ^= 1<<i;
		d1 ^= 1<<(n - 1 + i);
		d2 ^= 1<<(i);
	}

	int j;
	for (i = 0; i < 3; ++i) {
		for (j = 0; j < n; ++j)
			printf("%d ", sol&#91;i&#93;&#91;j&#93; + 1);
		printf("\n");
	}

	if ((n % 2 == 0) && (6 < n))
		solP *= 2;
	else if ((n % 2 == 1) && (n > 6))
		solP += temp;
	printf("%d\n", solP);

	return 0;
}

There are a few other optimisations littered throughout the code, but they’re not hard to understand. Good luck. Always open to comments.

P.S. This also is also called “The Queens Problem” or the like.