How do I solve the 'classic' knapsack algorithm recursively?

Question

This is my task

The Knapsack Problem is a classic in computer science. In its simplest form it involves trying to fit items of different weights into a knapsack so that the knapsack ends up with a specified total weight. You don't need to fit in all the items. For example, suppose you want your knapsack to weigh exactly 20 pounds, and you have five items, with weights of 11, 8, 7, 6, and 5 pounds. For small numbers of items, humans are pretty good at solving this problem by inspection. So you can probably figure out that only the 8, 7, and 5 combination of items adds up to 20.

I really don't know where to begin writing this algorithm. I understand recursion when applied to factorials and triangle numbers. However I'm lost right now.

Answer 1

What did you try?

The idea, given the problem you stated (which specifies we must use recursion) is simple: for each item that you can take, see if it's better to take it or not. So there are only two possible path:

1. you take the item
2. you don't take it

When you take the item, you remove it from your list and you decrease the capacity by the weight of the item.

When you don't take the item, you remove if from you list but you do not decrease the capacity.

Sometimes it helps to print what the recursive calls may look like. In this case, it could look like this:

Calling 11 8 7 6 5  with cap: 20
 +Calling 8 7 6 5  with cap: 20
 |  Calling 7 6 5  with cap: 20
 |    Calling 6 5  with cap: 20
 |      Calling 5  with cap: 20
 |      Result: 5
 |      Calling 5  with cap: 14
 |      Result: 5
 |    Result: 11
 |    Calling 6 5  with cap: 13
 |      Calling 5  with cap: 13
 |      Result: 5
 |      Calling 5  with cap: 7
 |      Result: 5
 |    Result: 11
 |  Result: 18
 |  Calling 7 6 5  with cap: 12
 |    Calling 6 5  with cap: 12
 |      Calling 5  with cap: 12
 |      Result: 5
 |      Calling 5  with cap: 6
 |      Result: 5
 |    Result: 11
 |    Calling 6 5  with cap: 5
 |      Calling 5  with cap: 5
 |      Result: 5
 |    Result: 5
 |  Result: 12
 +Result: 20
  Calling 8 7 6 5  with cap: 9
    Calling 7 6 5  with cap: 9
      Calling 6 5  with cap: 9
        Calling 5  with cap: 9
        Result: 5
        Calling 5  with cap: 3
        Result: 0
      Result: 6
      Calling 6 5  with cap: 2
        Calling 5  with cap: 2
        Result: 0
      Result: 0
    Result: 7
    Calling 7 6 5  with cap: 1
      Calling 6 5  with cap: 1
        Calling 5  with cap: 1
        Result: 0
      Result: 0
    Result: 0
  Result: 8
Result: 20

I did on purpose show the call to [8 7 6 5] with a capacity of 20, which gives a result of 20 (8 + 7 + 5).

Note that [8 7 6 5] is called twice: once with a capacity of 20 (because we didn't take 11) and once with a capacity of 9 (because with did take 11).

So the path to the solution:

11 not taken, calling [8 7 6 5] with a capacity of 20

8 taken, calling [7 6 5] with a capacity of 12 (20 - 8)

7 taken, calling [6 5] with a capacity of 5 (12 - 7)

6 not taken, calling [5] with a capacity of 5

5 taken, we're at zero.

The actual method in Java can fit in very few lines of code.

Since this is obviously homework, I'll just help you with a skeleton:

private int ukp( final int[] ar, final int cap ) {
    if ( ar.length == 1 ) {
        return ar[0] <= cap ? ar[0] : 0;
    } else {
        final int[] nar = new int[ar.length-1];
        System.arraycopy(ar, 1, nar, 0, nar.length);
        fint int item = ar[0];
        if ( item < cap ) {
            final int left = ...  // fill me: we're not taking the item
            final int took = ...  // fill me: we're taking the item
            return Math.max(took,left);
        } else {
            return ... // fill me: we're not taking the item
        }
    }
}

I did copy the array to a new array, which is less efficient (but anyway recursion is not the way to go here if you seek performance), but more "functional".

Answer 2

I had to do this for my homework so I tested all of the above codes (except for the Python one), but none of them work for every corner case.

This is my code, it works for every corner case.

static int[] values = new int[] {894, 260, 392, 281, 27};
static int[] weights = new int[] {8, 6, 4, 0, 21};
static int W = 30;

private static int knapsack(int i, int W) {
    if (i < 0) {
        return 0;
    }
    if (weights[i] > W) {
        return knapsack(i-1, W);
    } else {
        return Math.max(knapsack(i-1, W), knapsack(i-1, W - weights[i]) + values[i]);
    }
}

public static void main(String[] args) {
System.out.println(knapsack(values.length - 1, W));}

It is not optimized, the recursion will kill you, but you can use simple memoization to fix that. Why is my code short, correct and simple to understand? I just checked out the mathematical definition of the 0-1 Knapsack problem http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming