How to Solve the 'Classic' Knapsack Algorithm Recursively

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

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".

Knapsack Solution using Recursion

Please consider accepting amit's solution as the answer, I just want to supplement additional note on top of his solution here.

In this solution, I will also cater the case when the knapsack solution is not unique.

As pointed out by amit, it is straight-forward to modify your code to keep track of the elements in the knapsack. Your method should return a tuple instead of the knapsack value, where the first entry is the "max value" of the knapsack, and the second entry is a list of list of elements in the knapsack that represents of the combinations of items in the knapsack.

• The first if corresponds to the termination condition of the recursion, and there is only one possible combination in the knapsack - knapsack without any element.
• If the condition of the second if is true, then item n - 1 cannot be picked so we recur to the next item.
• On the other hand, if the weight of item n - 1 is less than availableMoney, then we can either pick item n - 1 in the construction (this corresponds to element1), or leave item n - 1 out in the construction. The returned solution should then be the better one of the two, or merging them together if they give the same value.

Below is a modified version of code for your reference:

def knapsack(availableMoney: Int, wt: List[Int], value: List[Int], n: Int): (Int, List[List[Int]]) = {

  if (n == 0 || availableMoney == 0)
    return (0, List[List[Int]](List[Int]()))

  if (wt(n - 1) > availableMoney) {
    return knapsack(availableMoney, wt, value, n - 1)
  } else {
    val recur = knapsack(availableMoney - wt(n - 1), wt, value, n - 1)
    val element1 = (recur._1 + value(n - 1), for (e <- recur._2) yield {e :+ wt(n - 1)})
    val element2 = knapsack(availableMoney, wt, value, n - 1)

    if (element1._1 > element2._1)
      return element1
    else if (element1._1 < element2._1)
      return element2
    else
      return (element1._1, element1._2 ::: element2._2)
  }
}

Recursive Knapsack Java

The problem you described is actually a special case where you have only items weights, but no profits - or alternatively the weights and the profits are equal. This problem isusually not termed as Knapsack but the maximization version of Subset Sum.

Furthermore, for a recursive solution no array besides the input is needed.

Suppose the item sizes are given in the array weightArray (indices zero-based here) of length n and capacity denoted the total capacity availabel.

Define (first conceptually, not in code) the function

F( remainingCapacity, i ) :=
maximum total weight attainable for items
with indices in {0,..,i} of infinity if no such solution exists

note that

F( capacity, n - 1 )

yields the solution to the problem. Additionally, F has the property

F( remainingCapacity, -1 ) = 0 if remainingCapacity >= 0 

and

F( remainingCapacity, i ) =
Infinity (can be simulated by a sufficiently
large integer) if remainingCapacity < 0

and

F( remainingCapacity, i ) =
max( F( remainingCapacity - weightArray[ i ], i - 1 ),
     F( remainingCapacity, i - 1 ) )

where the first term in the maximum expression corresponds to the "take item i" case and the second expression corresponds to the "don't take item i" case. The cases above can more or less easily transformed to an actual implementation.

However note that this will yield only the maximum value attainable by a choice of items, but not the actual choice of items itself.

I'm trying to solve the knapsack problem using Java and recursion

What is happening in your code is that when it gets to the last else statement, it is not removing the initial value that was put in. I made a small change to your code that may get you the results you are looking for. First, I had the recursive function return an int, which would be the capacity:

 public static int recknapSack(int capacity, int[] items, int branch) {

I changed every return statement to:

 return capacity;

Then inside of the else statement, I added the following:

 else {

             int firstItem; // this the first item, it will either be discarded (not included) or placed in the sack array (included)
             firstItem = items[0];

             items = Arrays.copyOfRange(items, 1, items.length); // for either recursive branch: remove the first item from the list

             recknapSack(capacity, items, 1); // call recursive function, left branch, where item is discarded and not placed in sack

             // prepare for right branch, where item is placed in sack
             capacity -= firstItem; // subtract the left most item weight from from capacity
             int temp = pos;
             sack[pos++] = firstItem; // place the item in the sack
             System.out.println("First item " + firstItem);
             int ret = recknapSack(capacity, items, 2); // recursive right branch call, item is placed in sack, weight subtracted from capacity
             if(ret != 0)
             {
                  System.out.println("Removing " + sack[temp] + " at position " + (temp));
                 sack[temp] = 0;
                 pos = temp;
             }

      }

This will keep the sack the same unless the capacity were not 0. You are still removing everything from the sack if you find it to be 0, so if you need to store that information, I would suggest that in the situation where it does work, you store the sack into an ArrayList of arrays that will contain all of the perfect solutions. If you need solutions in a situation where there is no perfect solution, you can also store every solution in there and have it ordered by the lowest capacity.

Hope that helps.

Adding a cache array to recursive knapsack solution?

(A) Why the current solution is behaving this way

• self.array is an instance attribute that is shared by all recursion paths. On one path or another each item is taken and so a one is appended to the list.
• option_A = val[index]... takes an item but doesn't append a one to the list.
• option_B = self..... skips an item but doesn't append a zero to the list.
• if option_A > option_B: When you make this comparison you have lost the information that made it - the items that were taken/discarded in the branch;
  
  • in the suites you just append a one or a zero regardless of how many items made those values.
  • The ones and zeroes then represent whether branch A (1) or branch B (0) was successful in the current instance of the function.

(B) How the code can be restructured such that a one-hot "take or don't take" vector can be captured, representing whether a given item goes in the knapsack or not.

It would be nice to know what you have taken after running through the analysis, I suspect that is what you are trying to do with self.array. You expressed an interest in OOP: instead of keeping track with lists of numbers using indices to select numbers from the lists, make objects to represent the items work with those. Keep the objects in containers and use the functionality of the container to add or remove items/objects from it. Consider how you are going to use a container before choosing one.

• Don't put the function in a class.
• Change the function's signature to accept
  
  • available weight,
  • a container of items to be considered,
  • a container holding the items currently in the sack (the current sack).
• Use a collections.namedtuple or a class for the items having value and weight attributes.
  
  • 
    

    Item = collections.namedtuple('Item',['wt','val'])
    

• When an item is taken add it to the current sack.
• When recursing
  
  • if going down the take path add the return value from the call to the current sack
  • remove the item that was just considered from the list of items to be considered argument.
  • if taken subtract the item's weight from the available weight argument
• When comparing two branches you will need to add up the values of each item the current sack.
  
  • return the sack with the highest value
• carefully consider the base case

---

Make the items to be considered like this.

import collections
Item = collections.namedtuple('Item',['wt','val'])
items = [Item(wght,value) for wght,value in zip(wt,val)]

Add up values like this.

value = sum(item.val for item in current_sack)
# or
import operator
val = operator.itemgetter('val')
wt = operator.itemgetter('wt')
value = sum(map(val,current_sack)

---

Your solution enhanced with debugging prints for the curious.

class Solution:
    def __init__(self):
        self.array = []
        self.other_array = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
    
    def knapSack(self,W, wt, val, n,j=0):
        index = n-1 
        deep = f'''{' '*j*3}'''
        print(f'{deep}level {j}')
        print(f'{deep}{W} available: considering {wt[index]},{val[index]}, {n})')
        # minor change here but has no affect on the outcome0
        #if n == 0 or W == 0 :
        if n == 0:
            print(f'{deep}Base case found')
            return 0
        print(f'''{deep}{wt[index]} > {W} --> {wt[index] > W}''')
        if (wt[index] > W):
            print(f'{deep}too heavy')
            self.array.append(0)
            self.other_array[index] = 0
            choice = self.knapSack(W, wt, val, index,j+1) 

        else:
            print(f'{deep}Going down the option A hole')
            option_A = val[index] + self.knapSack( W-wt[index], wt, val, index,j+1)
            print(f'{deep}Going down the option B hole')
            option_B = self.knapSack(W, wt, val, index,j+1)
            print(f'{deep}option A:{option_A} option B:{option_B}')
            if option_A > option_B:
                print(f'{deep}option A wins')
                self.array.append(1)
                self.other_array[index] = 1
                choice = option_A
            else:             
                print(f'{deep}option B wins')
                self.array.append(0)
                self.other_array[index] = 0
                choice = option_B

        print(f'{deep}level {j} Returning value={choice}')
        print(f'{deep}---------------------------------------------')
        return choice

trouble with solving knapsack issue recursively in C

The program is incorrect, see this line:

if (profit[n] > capacity)
    return knapsackRecursive(capacity, mass, profit, n-1);

Here you compare profit with capacity. You should compare with mass[n]. The rest of the code looks ok for now.

Perhaps you better use the maximum of a library and not the "ternary operator", since such operator creates branches whereas sometimes maximum can be done without branching.

A problem with the program you can perhaps try to resolve is at least generate the bag and print it. You can also use instance of the Knapsack problem with a known solution.

Printing out result in 0/1 KnapSack (Recursive Brute Force)

To track the items taken, try something like:

public static int KnapSack(int capacity, Item[] items, int numItems, ArrayList<Integer> taken) {
    if (numItems == 0 || capacity == 0)
        return 0;
    if (items[numItems-1].weight > capacity)
        return KnapSack(capacity, items, numItems-1, taken);
    else {
        final int preTookSize = taken.size();
        final int took = items[numItems-1].value + KnapSack(capacity - items[numItems-1].weight, items, numItems-1, taken);

        final int preLeftSize = taken.size();
        final int left = KnapSack(capacity, items, numItems-1, taken);

        if (took > left) {
            if (taken.size() > preLeftSize)
                taken.removeRange(preLeftSize, taken.size());
            taken.add(Integer.valueOf(numItems - 1));
            return took;
        }
        else {
            if (preLeftSize > preTookSize)
                taken.removeRange(preTookSize, preLeftSize);
            return left;
        }
    }     
}

This may not be the most efficient, but I think it should work.

(For efficiency you might try pre-allocating the taken ArrayList to be "big enough" such that no allocations need to happen during the recursive looping.)

---

Related Topics