0 1 Knapsack

This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion.

We will consider every subset of the given items and calculate the weight and value of each subset. We will consider only those subsets whose total weight is smaller than or equal to ‘W’. Finally, pick the subset with the maximum value. 

The base case of the recursion would be when no items are left or the remaining capacity of the knapsack is 0. 

How to generate subsets? 

The thief has two options for each item, either pick it or leave it. 

Thus, there are two cases for each item: 

1. Include the item in the set and recur for the remaining items with the decreased capacity of the knapsack.
2. Do not include the item and recur for the remaining items.

Note that we can only include an item in the set if and only if the weight of the item is less than or equal to the remaining weight of the knapsack. 

Finally, return the maximum value of the items in the knapsack obtained by including or excluding the current item. 

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again. 

Lets understand by an example:

Suppose there are 3 items with weights [2, 2, 3] and the capacity of the knapsack is 5.

The below figure shows some of the recursive calls made for the given problem. 

Representation format : N, [weights], W

As we can see, some subproblems are called multiple times. 

Same subproblems are shown by the same colour.

That’s why we are storing the solved subproblems in a lookup table so that we don’t have to solve them again. Whenever a call is made to the solved subproblem, we will directly return the answer of that subproblem stored in the lookup table.

Algorithm: 

• The idea is to use memoization.
• Create a 2-D lookup table of size (N + 1) * (W + 1) where N is the number of items and W is the maximum weight the thief can carry. Lookup table stores the solutions to the subproblems where lookUp[i][j] denotes the maximum profit the thief can earn by considering up to first 'i' items whose combined weight is less than or equal to 'j'.
• Initialize the table by -1.
• Now, we will call a recursive function 'maxProfitHelper’ that takes the items, weights, and capacity of the knapsack. This function will generate all possible subsets and will return the maximum profit the thief can earn.

Algorithm for the maxProfitHelper function:

• Base condition:  When no items are left or the remaining capacity of the knapsack is 0.
• If the current subproblem has been solved already, return the value stored in the lookUp table.
  Means, if lookUp[i][W] != -1, return lookUp[i][W].
• Now recursively generate all subsets and find the maximum profit by,
  • Including the item in the set and recur for the remaining items with the decreased capacity of the knapsack.
  • Not including the item and recur for the remaining items.
• Note that we can only include an item in the set if and only if the weight of the item is less than or equal to the remaining weight of the knapsack.
• 'result' is the maximum profit obtained by either including the current item in the knapsack or excluding the current item.
• Store the answer in the lookup table as lookUp[i][W] = result.
• Finally, return the ‘answer’.

Initially, we were breaking the large problem into small problems but now, let us look at it in a different way. Can you solve the small problem first and then reach the final answer? Try to use the bottom-up approach now. 

Algorithm: 

• The idea is to create a 2-D array ‘result’ of size size (N + 1) * (W + 1).
• Initially, all the elements of the ‘result’ matrix will be 0.
• Now, the value result[i][j] denotes the maximum profit the thief can earn considering upto first 'i' items whose combined weight is less than or equal to 'j'.
• The detailed algorithm to fill the ‘result’ matrix is as follows:
  1. L1 : Run a loop from i = 1 to N to consider all the items.
  2. L2 : Run a loop from j = 0 to W to consider all weights from 0 to maximum capacity W.
     If the weight of the current item is more than j, we can not include it. 
     Thus, result[i][j] = result[i - 1][j].
     Else, find the maximum profit obtained by either including the current item or excluding the current item.
     i.e. result[i][j] = max(result[i - 1][j], values[i] + result[i - 1][j - weights[i]]). 
     Note that, when we are including an item, the capacity of the knapsack will be reduced by the weight of the included item. 
     Also note that L1, and L2 and will be two nested loops.
• Return result[N][W], the final profit that the thief can make.

Basically, in the previous approach, you can observe that:

• If you include the item i with total knapsack weight being j:
  1. You look for the previous row of the 2D matrix with the required column i.e. result[i - 1][ j - weights[ i ]].
• If you exclude the item i with total knapsack weight being j:
  1. You look for the previous row of the 2D matrix with the required column i.e. result[i - 1][ j ].

You can observe 2 things here:

• We only need to know about the previously filled row.
• For the jth column, we need information about columns less than j only. In simple terms, when we include an item, we go to the previous row and (j - weights[i])th column. It should be noted that j - weights[i] is always less than j. Thus, we need to iterate from backwards. This point will be more clear when you see the algorithm.

Algorithm

• Create an array ‘results’ of size (W + 1).
• Initially, all the elements of the ‘result’ array will be 0.
• Now, the final value of result[ j ] denotes the maximum profit the thief can earn considering items whose combined weight is less than or equal to 'j'.
• The detailed algorithm to fill the ‘result’ array is as follows:
  1. L1: Run a loop from i = 1 to N to consider all the items:
  2. L2: Run a loop from j = W to (j >= weights[ i ]):
     1. Update results[ j ] as max( results[ j ], values[ i ] + results[ j - weights[ i ]]).
        Note that L1, and L2 and will be two nested loops.
• Return result[ W ], the final profit that the thief can make.