0-1 Knapsack problem (DP-07)

We are given a set of items, each item is associated with a weight and a value. We need to determine the number of each item to include in a knapsack so that the total weight of the final knapsack is less than or equal to a given limit W and the total value is maximum. Also, please note that the items are indivisible units which means that there are only two possible choice – either include or exclude the item.

Sample Input: Values = { 20, 5, 10, 40, 15, 25 }, Weights = { 1, 2, 3, 8, 7, 4 }, W = 10
Expected Output: 60
Explanation: Weight = 1 + 8 < 10 (W) and Value = 20 + 40 = 60

Algorithm:

  1. The problem can be solved using dynamic programming as it has optimal substructure and overlapping sub problem.
  2. For each item we have two possibilities, either we include the current item in the knapsack, add the value and weight of the current item to the total value and weight and then recur for remaining items with decreased capacity.
    Or we can exclude the current item from knapsack and recur for remaining items.
  3. Finally, we return the maximum value by including or excluding the current item.
  4. The following implementation is a bottom up approach of the same problem.
  5. We create a 2D array DP of size (n+1, w+1) where n is the total number of items and w is the weight limit of the knapsack.
  6. If the current element’s weight is greater than the remaining capacity, we exclude the item and retrieve the result of the previous sub problem.
  7. Else we find the maximum of the following conditions – either we exclude the current item or we include the current items value to the answer of the sub problem.
/* Author => Raunak Jain */
#include <bits/stdc++.h>
using namespace std;

int helper(vector<int> weights, vector<int> values, int w){
	int wsize = weights.size();
	vector<vector<int>> dp(wsize+1, vector<int>(w+1, 0));
	for(int i=1; i<=wsize; i++){
		for(int j=1; j<=w; j++){
			if(weights[i-1]>j){
				dp[i][j] = dp[i-1][j];
			}else{
				dp[i][j] = max(dp[i-1][j], values[i-1]+dp[i-1][j-weights[i-1]]);
			}
		}
	}
	return dp[wsize][w];
}

int main(){
	vector<int> values = { 60, 100, 120 }; 
	vector<int> weights = { 10, 20, 30 };
	int W = 50;
	cout<<helper(weights, values, W);
	return 0;
}

Also, check out another popular interview question Pots of Gold.

4 comments

Leave a Reply

Your email address will not be published.