0 1 Knapsack
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.

Constraints:

1

Question

0 1 Knapsack

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.

Constraints:

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.

Accepted Answer

In the Dynamic programming we will work considering the same cases as mentioned in the recursive approach. In a DP[][] table let’s consider all the possible weights from ‘1’ to ‘W’ as the columns and weights that can be kept as the rows.

The state DP[i][j] will denote maximum value of ‘j-weight’ considering all values from ‘1 to ith’. So if we consider ‘wi’ (weight in ‘ith’ row) we can fill it in all columns which have ‘weight values > wi’. Now two possibilities can take place:

1. Fill ‘wi’ in the given column.

2. Do not fill ‘wi’ in the given column.

Now we have to take a maximum of these two possibilities, formally if we do not fill ‘ith’ weight in ‘jth’ column then DP[i][j] state will be same as DP[i-1][j] but if we fill the weight, DP[i][j] will be equal to the value of ‘wi’+ value of the column weighing ‘j-wi’ in the previous row. So we take the maximum of these two possibilities to fill the current state.

Accepted Answer

Recursion

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:

Include the item in the set and recur for the remaining items with the decreased capacity of the knapsack.
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.

Space Complexity: OtherExplanation:

O(N), where N is the number of items.

We are not using any external data structure. Only recursion stack space of O(N) size is used by the algorithm.

Time Complexity: OtherExplanation:

O(2 ^ N), where N is the number of items.

There are N items available and for each item, we can either include it or exclude it. In the worst case, we will be generating every possible subset of the given items. Thus, the final time complexity is O(2 ^ N).

Accepted Answer

Memoization

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

Space Complexity: OtherExplanation:

O(N * W), where N is the number of items and W is the maximum capacity of the knapsack.

We are using a lookup table of size (N + 1) * (W + 1) to store the solutions of the subproblems. Also, recursion stack space of O(N) size is used. Thus, the final space complexity is O( N * W + N) = O(N * W).

Time Complexity: OtherExplanation:

O(N * W), where N is the number of items and W is the maximum capacity of the knapsack.

In the worst case, we will not have more than (N * M) distinct sequences. Thus, there will be at most (N * W) distinct calls and in each call, we are doing a constant amount of work. Thus, the final time complexity will be O(N * W).

Python (3.5)

'''

	Time Complexity: O(N * W)

	Space Complexity: O(N * W)



	Where N is the number of items and W is the capacity of the knapsack.

'''





def maxProfitHelper(values, weights, currIndex, w, lookUp):



    # Base condition

    if(currIndex == len(values) or w == 0):

        return 0



    # If we have already solved this subproblem

    if(lookUp[currIndex][w] != -1):

        return lookUp[currIndex][w]



    result = 0



    # If the weight of the current item is less than or equal to the capacity of the knapsack

    if(weights[currIndex] <= w):



        # Max profit by including the current item

        include = values[currIndex] + maxProfitHelper(

            values, weights, currIndex + 1, w - weights[currIndex], lookUp)



        # Max Profit by excluding the current item

        exclude = maxProfitHelper(values, weights, currIndex + 1, w, lookUp)



        result = max(include, exclude)



    else:



        # We can't include the current item

        result = maxProfitHelper(values, weights, currIndex + 1, w, lookUp)



    # Store the result

    lookUp[currIndex][w] = result



    # Return the maximum profit

    return result





def maxProfit(values, weights, n, w):



    lookUp = [[-1 for i in range(w + 1)] for j in range(n + 1)]

    return maxProfitHelper(values, weights, 0, w, lookUp)

Java (SE 1.8)

/*

	Time Complexity: O(N * W)
	Space Complexity: O(N * W)

	Where N is the number of items and W is the capacity of the knapsack.

*/

import java.util.ArrayList;

public class Solution {
	private static int maxProfitHelper(ArrayList values, ArrayList weights, int currIndex, int w,
			ArrayList> lookUp) {
		// Base condition
		if (currIndex == values.size() || w == 0) {
			return 0;
		}

		// If we have already solved this subproblem
		if (lookUp.get(currIndex).get(w) != -1) {
			return lookUp.get(currIndex).get(w);
		}

		int result = 0;

		// If the weight of the current item is less than or equal to the capacity of
		// the knapsack
		if (weights.get(currIndex).intValue() <= w) {
			// Max profit by including the current item
			int include = values.get(currIndex)
					+ maxProfitHelper(values, weights, currIndex + 1, w - weights.get(currIndex), lookUp);

			// Max Profit by excluding the current item
			int exclude = maxProfitHelper(values, weights, currIndex + 1, w, lookUp);

			// Update the result
			result = Math.max(include, exclude);
		} else {
			// We can't include the current item
			result = maxProfitHelper(values, weights, currIndex + 1, w, lookUp);

		}

		// Store the result
		lookUp.get(currIndex).set(w, result);

		// Return final profit
		return result;
	}

	public static int maxProfit(ArrayList values, ArrayList weights, int n, int w) {

		ArrayList> lookUp = new ArrayList>();

		for (int i = 0; i < n + 1; i++) {
			ArrayList temp = new ArrayList();
			for (int j = 0; j < w + 1; j++) {
				temp.add(-1);
			}

			lookUp.add(temp);
		}
		return maxProfitHelper(values, weights, 0, w, lookUp);
	}
}

C++ (g++ 5.4)

/*



	Time Complexity: O(N * W)

	Space Complexity: O(N * W)



	Where N is the number of items and W is the capacity of the knapsack.



*/



int maxProfitHelper(vector &values, vector &weights, int currIndex, int w, vector> &lookUp)

{

	// Base condition

	if (currIndex == values.size() || w == 0)

	{

		return 0;

	}



	// If we have already solved this subproblem

	if (lookUp[currIndex][w] != -1)

	{

		return lookUp[currIndex][w];

	}



	int result = 0;



	// If the weight of the current item is less than or equal to the capacity of the knapsack

	if (weights[currIndex] <= w)

	{

		// Max profit by including the current item

		int include = values[currIndex] + maxProfitHelper(values, weights, currIndex + 1, w - weights[currIndex], lookUp);



		// Max Profit by excluding the current item

		int exclude = maxProfitHelper(values, weights, currIndex + 1, w, lookUp);



		result = max(include, exclude);

	}

	else

	{

		// We can't include the current item

		result = maxProfitHelper(values, weights, currIndex + 1, w, lookUp);

	}



	// Store the result

	lookUp[currIndex][w] = result;



	// Return the maximum profit

	return result;

}



int maxProfit(vector &values, vector &weights, int n, int w)

{

	vector> lookUp(n + 1, vector(w + 1, -1));



	return maxProfitHelper(values, weights, 0, w, lookUp);

}

Accepted Answer

Dynamic Programming

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.

Space Complexity: OtherExplanation:

O(N * W), where N is the number of items and W is the maximum capacity of the knapsack.

Since we are using a table ‘result’ of size (N) * (W), the final space complexity is O(N * W).

Time Complexity: OtherExplanation:

O(N * W), where N is the number of items and W is the maximum capacity of the knapsack.

For each item [ O(N) choices ], we are considering the full capacity of the knapsack [ O(W) choices ]. Including and excluding an item is done in O(1) time. Thus, the final time complexity is O(N * W).

Java (SE 1.8)

/*

	Time Complexity: O(N * W)
	Space Complexity: O(N * W)

	Where N is the number of items and W is the capacity of the knapsack.

*/

import java.util.ArrayList;

public class Solution {

	public static int maxProfit(ArrayList values, ArrayList weights, int n, int w) {

		ArrayList> result = new ArrayList>();

		for (int i = 0; i < n + 1; i++) {
			ArrayList temp = new ArrayList();
			for (int j = 0; j < w + 1; j++) {
				temp.add(0);
			}

			result.add(temp);
		}

		// Loop to consider all items
		for (int i = 1; i <= n; i++) {

			// Loop to consider all weights from 0 to maximum capacity of the knapsack
			for (int j = 1; j <= w; j++) {

				// If the weight of the item is less than or equal to the capacity of the
				// knapsack
				if (weights.get(i - 1).intValue() <= j) {
					// Maximum profit by including or excluding the current item

					result.get(i).set(j, Math.max(result.get(i - 1).get(j),
							values.get(i - 1) + result.get(i - 1).get(j - weights.get(i - 1))));
				} else {
					// We can't include the item
					result.get(i).set(j, result.get(i - 1).get(j));
				}
			}
		}

		// Return the final profit
		return result.get(n).get(w);
	}
}

Python (3.5)

'''

	Time Complexity: O(N * W)

	Space Complexity: O(N * W)



	Where N is the number of items and W is the capacity of the knapsack.

'''





def maxProfit(values, weights, n, w):



    result = [[0 for i in range(w + 1)] for j in range(n + 1)]



    # Loop to consider all items

    for i in range(1, n + 1):



        # Loop to consider all weights from 0 to maximum capacity of the knapsack

        for j in range(1, w + 1):



            # If the weight of the item is less than or equal to the capacity of the knapsack

            if(weights[i - 1] <= j):



                # Maximum profit by including or excluding the current item

                result[i][j] = max(result[i - 1][j], values[i - 1] +

                                   result[i - 1][j - weights[i - 1]])



            else:



                # We can't include the item

                result[i][j] = result[i - 1][j]



    # Return the final profit

    return result[n][w]

C++ (g++ 5.4)

/*



	Time Complexity: O(N * W)

	Space Complexity: O(N * W)



	Where N is the number of items and W is the capacity of the knapsack.



*/



int maxProfit(vector& values, vector& weights, int n, int w)

{

	vector> result(n + 1, vector (w + 1, 0));



	// Loop to consider all items

    for(int i = 1; i <= n; i++)

    {

    	// Loop to consider all weights from 0 to maximum capacity of the knapsack

    	for(int j = 1; j <= w; j++)

    	{

    		// If the weight of the item is less than or equal to the capacity of the knapsack 

            if(weights[i - 1] <= j)

    		{

    			// Maximum profit by including or excluding the current item 

    			result[i][j] = max(result[i - 1][j], values[i - 1] + result[i - 1][j - weights[i - 1]]);

    		}

    		else

    		{

    			// We can't include the item 

    			result[i][j] = result[i - 1][j];

    		}

    	}

    }



    // Return the final profit 

    return result[n][w];

}

Accepted Answer

Space Optimized DP

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.

Space Complexity: OtherExplanation:

O(W), where W is the maximum capacity of the knapsack.

Since we are using a linear array ‘result’ of size (W), the final space complexity is O(W).

Time Complexity: OtherExplanation:

O(N * W), where N is the number of items and W is the maximum capacity of the knapsack.

For each item [ O(N) choices ], we are considering the full capacity of the knapsack [ O(W) choices ]. Including and excluding an item is done in O(1) time. Thus, the final time complexity is O(N * W).

C++ (g++ 5.4)

/*



	Time Complexity: O(N * W)

	Space Complexity: O(W)



	Where N is the number of items and W is the capacity of the knapsack.



*/



int maxProfit(vector& values, vector& weights, int n, int w)

{

	vectorresult(w + 1, 0); 

  

    // Loop to consider all the items 

    for(int i=0; i < n; i++)

    {

    	// Loop to consider all the weights 

    	for(int j = w; j >= weights[i]; j--)

    	{

    		result[j] = max(result[j], values[i] + result[j - weights[i]]);

    	}

    }  

     

    // Return the final maximum profit 

    return result[w]; 

}

Python (3.5)

'''

	Time Complexity: O(N * W)

	Space Complexity: O(W)



	Where N is the number of items and W is the capacity of the knapsack.

'''





def maxProfit(values, weights, n, w):



    result = [0] * (w + 1)



    # Loop to consider all the items

    for i in range(n):



        # Loop to consider all the weights

        for j in range(w, weights[i] - 1, -1):



            result[j] = max(result[j], values[i] + result[j - weights[i]])



    # Return the final maximum profit

    return result[w]

Java (SE 1.8)

/*

	Time Complexity: O(N * W)
	Space Complexity: O(W)

	Where N is the number of items and W is the capacity of the knapsack.

*/

import java.util.ArrayList;

public class Solution {

	public static int maxProfit(ArrayList values, ArrayList weights, int n, int w) {

		ArrayList result = new ArrayList();

		for (int i = 0; i < w + 1; i++) {
			result.add(0);
		}

		// Loop to consider all the items
		for (int i = 0; i < n; i++) {
			// Loop to consider all the weights
			for (int j = w; j >= weights.get(i); j--) {
				result.set(j, Math.max(result.get(j), values.get(i) + result.get(j - weights.get(i))));
			}
		}

		// Return the final maximum profit
		return result.get(w);
	}
}

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:

Output Format :

Constraints:

Top Nagarro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Nagarro Software Developer