The Knapsack Problem
Written by Mike James   
Tuesday, 19 January 2010
Article Index
The Knapsack Problem
Knapsack solved

 

I like problems that look simple and turn out to be really difficult. It's the way that something simple can hide a complexity that you never guessed at. Fortunately for me the universe seems to be built in this way!

One particularly fascinating problem that also has applications in cryptography is the knapsack or sum partitioning problem. It is very like the challenge posed on some quiz shows where the contestants have use a randomly picked set of numbers and the four arithmetic operators to get as close as possible to a target.

On the face of it the knapsack problem is even simpler than this – given a set of positive integers 3, 5, 6, 10, 34 say, find a subset that sums to exactly to a given value, 50 say. In this case you should spot at once that 34+10 is 44 and 44+6 is 50 so the subset in question is 6,10,34.

This is called the knapsack problem because it is the same as trying to pack a knapsack with a range of items, i.e. the positive integers, so that it is just full, i.e. reaches the value in question.

Easy as I said but now try to write a computer program that, given an arbitrary set of n positive integers, finds a subset that sums to a given integer.There are many clever ways of doing this but the most direct is simply to examine all the possible ways of adding the numbers up. This approach may not be clever but it demonstrates why the task is difficult and reveals a number of deeper principles.

The first problem that you face is that you need to try every possible subset of n numbers. If you want all possible subsets of three numbers then the easiest way in C# is to write three for loops:

 for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
for (int k = 1; k <= 3; k++)
Console.WriteLine(i.ToString()
+ "," + j.ToString() +
"," + k.ToString());

Actually this generates more than the subsets because it generates values like 1,1,1 and 1,2,3 and 3,2,1 – but it works and you can get rid of the sillies and the duplicates easily. The problem is that for n numbers you can't have a variable number of for loops. Whenever you find yourself looking at a variable number of for loops you have to solve the problem using recursion.

You could say that it a problem involving n objects requiring n nested loops to solve it is a "smell" that recursion is in the air.

Before moving on to the knapsack problem let's implement a simple function that uses recursion to create N nested loops - where N is a variable.

The function we need creates a new loop each time it is called, i.e. increasing the number of loops and hence the nesting by one.

 void Loop(int nest, int N)
{

The first parameter records the current nesting level and the second the desired nesting level. That is, the function will create N nested loops.

If the current nesting level is equal or greater than N we don't want to create another loop:

 if (nest >= N)return;

If we do need a new loop add one to the nesting level and create a new loop:

 nest++;
int i;
for (i = 0; i < N; i++)
{

To see that the nested loops are doing what we think they are the loop prints its nesting level and current value:

  Console.WriteLine("Nesting " +
nest.ToString() +
" Value " + i.ToString());

Finally we use the Loop function once again, i.e. recursively to create another loop inside the current loop:

  Loop(nest,N);
}
Console.WriteLine();
nest--;

When the loop ends we simple throw a new line and decrement the nesting count.

The complete function is:

void Loop(int nest, int N)
{
 if (nest >= N)return;
 int i;
 nest++;
 for (i = 0; i < N; i++)
 {
 Console.WriteLine("Nesting " +
nest.ToString() + " Value " +
i.ToString());
  Loop(nest,N);
}
Console.WriteLine();
nest--;
}

and to use it you simple set the current nesting level to 0 i.e. there are no loops when you start and the desired nesting level to three say:

 Loop(0,3);

The result in this case is:

 Nesting 1 Value 0
 Nesting 2 Value 0
Nesting 3 Value 0
Nesting 3 Value 1
Nesting 3 Value 2
 Nesting 2 Value 1
Nesting 3 Value 0
Nesting 3 Value 1
Nesting 3 Value 2
 Nesting 2 Value 2
Nesting 3 Value 0
Nesting 3 Value 1
Nesting 3 Value 2
 ...
and so on

Notice that the highest nested loop index changes fastest which is what you would expect of a set of nested loops.

<ASIN:3540402861>

<ASIN:0471816523>

<ASIN:1848000693>



Last Updated ( Wednesday, 31 March 2010 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.