0-1 Knapsack Problem

#cpp

0-1 Knapsack problem is one of the most important problems based on the concept of Dynamic programming. Dynamic Programming(DP) is an algorithmic concept for solving optimization problems. In simple words, we try to break problems into subproblems and find their optimal solution which leads to the optimal overall solution. Let's understand the problem statement first.

Problem Description

Given n weights having a certain value put these weights in a knapsack with a given capacity (maxWeight). The total weight of the knapsack after adding weights must remain smaller than or equal to capacity(maxWeight). The goal here is to find possible maximum total value in the knapsack. Any weight can be selected only once. For example :

Input:
n=4
maxWeight=5
weights={4,3,5,1}
value={1,2,2,3}

Output:
5

In the above example, weights:{3,1} with value:{2,3} respectively will have a total value of 5 which is the maximum among any combination of weights.

Observation

Here the key observation is that we need to find the subset of weights whose weight sum is less than or equal to the capacity of the knapsack and having maximum value sum.

Recursive Approach

Recursively we will move from index 0 to n-1 and will perform two operations:

Add the current weight (Add element to a subset). We will only select the current weight if the total weight inside the knapsack after selecting remains under the given capacity else will ignore it.
Don't Add the current weight (Don't add an element to a subset).

We will recursively call the next element after performing may be any one or both operations given above as per the conditions. We will return the maximum of both operations as we have to find the maximum total value. We have to stop and return when we reach beyond the array size. So in the end, we will have a maximum of all such subsets where we made choices to select the weight with a certain value or ignore it.

        int rec_helper(int curWeightSum,int i,int n,int wt[],int val[],int maxWeight,int **dp){
            if(i==n){
                return 0;
            }
            if(dp[i][curWeightSum]!=-1){
                return dp[i][curWeightSum];
            }

            dp[i][curWeightSum] = rec_helper(curWeightSum,i+1,n,wt,val,maxWeight,dp);

            if(curWeightSum+wt[i]<=maxWeight) {
                dp[i][curWeightSum] = max(dp[i][curWeightSum],
                                          val[i] + rec_helper(curWeightSum + wt[i], i + 1, n, wt, val, maxWeight, dp));
            }

            return dp[i][curWeightSum];
        }

        int knapsack(int n,int wt[],int val[],int maxWeight){
            int** dp=new int*[n];
            for(int i=0;i<n;i++){
                dp[i]=new int[maxWeight+1];

                for(int j=0;j<maxWeight+1;j++){
                    dp[i][j]=-1;
                }
            }
            return rec_helper(0,0,n,wt,val,maxWeight,dp);
        }

Memoization - Here I used a 2d array - 'dp' to store the recursion calls so that we can use the stored value in dp for repeated recursion calls instead. This is useful for reducing time complexity.

Time Complexity : O(n*maxWeight). As we avoided most repeating calls.
Space Complexity : O(n*maxWeight). We used 2-d array dp as extra space

Dynamic Approach

Tabulation is done using a one-dimensional array in this case. Whose dimension is the same as maxWeight+1(capacity of knapsack). Here we do the same two operations stated in the recursive approach:

If we have to form a knapsack of capacity j and we have current weight under consideration as weights[i], which is <=j, with value[i]. If we add the current weights[i] in the knapsack, we need to find the maximum value for the knapsack of total weight (j-weight[i]) till previous iterations and then add value[i] of weights[i] weight in that. In case we don't have a knapsack of total weight (j-weights[i]) then 0 will be added and the value[i] of current weights[i] will become the total of values for that particular knapsack. If we have the current weight as 3 and required j=5 then we need to find a knapsack of weight 5-3=2.
If we don't select the weight, the value of that cell in dp array will be the answer to the previous iteration for that particular j.

int dp[maxWeight+1];
for(int i=0;i<maxWeight+1;i++){
   dp[i]=0;
}
for(int i=0;i<n;i++){
   for(int j=maxWeight;j>=wt[i];j--){
       dp[j]=max(dp[j],val[i]+dp[j-wt[i]]);
   }
}
return dp[maxWeight];

Here the cell value in the dp array will be the maximum of operation1 and operation2. I used 1-d array, where jth cell represents a knapsack with weight j while performing operations on a particular ith weight. Hence the array will hold results till (i-1)th weight while running for ith weight. Returning dp[maxWeight] will give the answer. Initially, all the values of the array is 0 as it will be the maximum for an empty knapsack.

Time Complexity : O(n*maxWeight).
Space Complexity : O(maxWeight). We used 2-d array dp as extra space