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.

There are a number of variations on the basic bounded problem - for example the unbounded problem lets you reuse a value more than once and this is easier to implement a solution to. 

What is interesting about the knapsack problem is that it is hard - NP hard to be exact. That is it is as hard or harder than any NP complete problem. The associated decision version of the problem - can the target number be made by selecting numbers from the list - is also NP complete. Don't worry if you don't know exactly what these mean - what is important is that there is no easy way to solve the Knapsack problem as far as we know. 

So solving the bounded problem, i.e. using each value at most once  in an effort to reach the target, is hard.

But as long as the number of values to be combined is small you can solve the problem using nothing but brute force. 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 (I'm using C# but its the same in other languages) 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 we are looking for because it generates values like 1,1,1, 1,1,2 and 1,2,3 and 3,2,1 – but it works and for the moment lets ignore the repeated values. 

However there is a more important problem with this approach. You can use this nested loop solution when the number of integers you are given is fixed i.e. it works fine for 3 numbers but not for n numbers.

You need to know the number of values you are going to be given well in advance of running the program. 

The problem is that for n numbers you need n nested loops and 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 a problem involving n objects requiring n nested loops to solve is a "smell" that recursion is in the air.

N Nested Loops As Recursion

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:

 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+1,N);
 }
 Console.WriteLine();


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;
 for (i = 0; i < N; i++){
   Console.WriteLine("Nesting " + 
                      nest.ToString() +
                     " Value " + 
                      i.ToString());
  Loop(nest+1,N);
 }
 Console.WriteLine();
}

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 0 Value 0
Nesting 1 Value 0
Nesting 2 Value 0
Nesting 2 Value 1
Nesting 2 Value 2

Nesting 1 Value 1
Nesting 2 Value 0
Nesting 2 Value 1
Nesting 2 Value 2

Nesting 1 Value 2
Nesting 2 Value 0
Nesting 2 Value 1
Nesting 2 Value 2

Nesting 0 Value 1
Nesting 1 Value 0
Nesting 2 Value 0
Nesting 2 Value 1
Nesting 2 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.

Notice that the power of this recursive function is that it can generate any number of nested loops. If you don't think that this is powerful try to do the same job without using recursion. It can be done but it's a mess of bookkeeping to track where you are in each loop. 

When people tell you how useful and how amazing recursion is keep in mind that it is its ability to create the equivalent of nested loops that is its special quality. 

Now that we know how to create an arbitrary number of nested loops the Knapsack problem is a lot more approachable. 

<ASIN:3540402861>

<ASIN:0471816523>

<ASIN:1848000693>