Page 2 of 2
Before we can create a Knapsack function we need some data to test it.
All we have to do is to load an array with a reasonable set of integers to try to make the target up from and it then calls the recursive SUM function which tries to find a subset:
int N = 50;
Random R = new Random();
int Target = R.Next(1,N * N);
int A = new int[N];
for (int i = 0; i < N; i++)
A[i] = R.Next(1,N * N / 2);
Console.WriteLine("Target: " +
int CurrentSum = 0;
Sum is recursive but not difficult to follow – it is just a set of nested for loops one per call of the function and is based on the Loop function listed earlier.
Now as well as nest and N we also need the CurrentSum, i.e. what the selected elements add up to, the array, and the Target value:
void Sum(int nest, int N,
ref int CurrentSum, int A,int Target)
if (nest >= N)return;
for (i = 0; i < N; i++)
The CurrentSum has to be passed by ref because it is changed by the function and this change needs to be returned to show what the result so far is. It is also what brings all of the loops to a stop. When we find a set of values that add to the Target that's enough, i.e. we are looking for the first solution not all of the solutions.
The logic in each loop is to first test to see if adding the next selected element will take the CurrentSum over the Target. If so we simply move on to the next element in the loop and see if this is worth considering:
if (CurrentSum + A[i] > Target)
If the current element can be added to the CurrentSum without exceeding the Target then we update the CurrentSum and call the function to find the next element using the next nested loop:
CurrentSum += A[i];
When this function returns it has either tested all of the elements and failed or it has found the correct sum, i.e. CurrentSum equals the Target and we test for this:
if (CurrentSum == Target)
"," + A[i].ToString());
If the CurrentSum is equal to the target we print the current index and the array element that was used in the sum and break out of the loop. Notice that once the CurrentSum is equal to the target it stays equal to the target and all of the loops come to an end by executing the break. If the inner loop fails to find a solution we have to correct CurrentSum by subtracting the failed element and moving on to try the next element in the loop.
CurrentSum -= A[i];
If you run it and it finds a solution it prints the elements of the array. If it fails to find a solution you just see the magic word "done" – you can't always make the target up from a subset of the values.
There are minor problems in this program – in particular it can generate repeated values in the set of numbers but this gets increasingly unlikely as N gets bigger.
If you try this program out you will find that at first everything works quickly with answers flashing up after a few seconds. However if you try N=30,000 say then things slow to a stop. The problem is that the knapsack algorithm slows down as 2^N which makes the problem for 30,000 number about 10^10000 (yes 1 followed by 10,000 zeros) times longer to solve than the 1000 number problem – so don't wait for a solution too long.
It is the huge number of different combinations that have to be considered that makes the task so difficult. However, how do you know that there isn't a short cut that means you don't have to consider every possible combination?
There are algorithms that attempt to solve the problem more quickly. For example there are variations on the greedy algorithm - pick the first number closest to the target, then the next closest and so on. A more sophisticated greedy algorithm is based on dynamic programming. The key factor in all of these algorithms is that they usually find the solution in reasonable time but there is no promise that they will ever find the solution without examining every possible combination. They may be advanced but they are still "heuristics", i.e. algorithms that usually work.
The knapsack problem is the basis for one method of public key cryptography. A set of numbers in a given order is made public and any user can code a message by multiplying each number by a zero or a one according to the messages binary representation. All of the values are added up to give a single value and this is of course the "target" value in a knapsack problem using the given set of numbers. Of course you can't decode the message because this would mean solving the knapsack problem for very very large N. However the intended recipient of the message can decode it because they have a "shadow" set of numbers with a special properties that make the solution of the knapsack problem very easy. So anyone can code a message using the public numbers but only the recipient can decode it without solving the full knapsack problem. Unfortunately a few years ago it was discovered that the need to use a "shadow" set of values made the knapsack problem posed by the public values rather easier to solve than was originally thought – i.e. there was a way of doing the job much faster than 2^N. So now the knapsack code is no longer used but it is still interesting and with a better set of shadow values might even be resurrected one day.