0 1 Knapsack

Posted: 7 Jan, 2021
Difficulty: Moderate


Try Problem

A thief is robbing a store and can carry a maximum weight of ‘W’ into his knapsack. There are 'N' items available in the store and the weight and value of each item is known to the thief. Considering the constraints of the maximum weight that a knapsack can carry, you have to find the maximum profit that a thief can generate by stealing items.

Note: The thief is not allowed to break the items.

For example, N = 4, W = 10 and the weights and values of items are weights = [6, 1, 5, 3] and values = [3, 6, 1, 4]. Then the best way to fill the knapsack is to choose items with weight 6, 1 and 3. The total value of knapsack = 3 + 6 + 4 = 13.

Input Format:
The first line contains a single integer 'T' representing the number of test cases.      
The 'T' test cases are as follows:

The first line contains two integers 'N' and 'W', denoting the number of items and the maximum weight the thief can carry, respectively. 
The second line contains 'N' space-separated integers, that denote the values of the weight of items. 
The third line contains 'N' space-separated integers, that denote the values associated with the items. 
Output Format :
The first and only line of output contains the maximum profit that a thief can generate, as described in the task. 
The output of every test case is printed in a separate line.
1 <= T <= 10
1 <= N <= 10^3
1 <= W <= 10^3
1<= weights <=10^3
1 <= values <= 10^3

where 'T' is the number of test cases, ‘N’ is the number of items, "weights" is the weight of each item, "values" is the value of each item and ‘W’ is the maximum weight the thief can carry. 
Approach 1

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. 

Try Problem