A Space Optimized DP solution for 0-1 Knapsack Problem

Problem Statement

We are given a knapsack which can hold some weight, we need to pick some of the items out of given items with some value. The items should be picked such that the value of the knapsack ( total value of picked up items ) should be maximized. We also need to take care that the weight of picked items does not exceed the value of the knapsack. Here, we can have a large knapsack weight. We cannot divide the items, i.e. we cannot take half part of an item or one-third. Thus, either we take an item or not which gives the problem its name 0-1 Knapsack Problem. Since knapsack can have large weight, find a space-optimized DP solution for 0-1 knapsack problem.

Example

Number of Items = 3
Weight of Knapsack = 4
Weight of given items = {4, 5, 1}
Value of given items = {10, 20, 30}

30

Explanation: We choose the last element because that gives us the best result (or maximum value)

Number of Items = 5
Weight of Knapsack = 50
Weight of given items = {10, 10, 10, 10, 10}
Value of given items = {1, 2, 3, 4, 5}

15

Explanation: We can simply choose all the items since our knapsack weight equals the total weight of all the items.

Approach for a space optimized DP solution for 0-1 Knapsack Problem

Generally, we solve 0-1 Knapsack using dynamic programming. This is one of the standard dynamic programming problems and many other standard dynamic programming problems follow the same pattern.

dp[i][j] = operation(dp[i-1][j], dp[i-1][j-wt[i] + val[i])

Here dp[i-1][j] represents we did not take the current item and

         dp[i-1][j-wt[i]] shows the reduced subproblem.

By operation I mean we generally either maximize a quantity or minimize the quantity.

The only problem which arises with this approach is its quadratic space complexity. We normally make a dp array or dp table of dimensions weight of knapsack x number of items. In cases where we are low on memory. We can further optimize our standard knapsack solution. Taking a look at the recursive formula gives us an insight that any state in the dp matrix depends on the cell just above it or left of it. Then we can just keep two rows of the dp table, the first current row, and second, the row before the current row. We can say the problem now boils down to using these two rows. We can work it out if we just use the second row for odd index rows and the first row for even index rows.

The approach told here will be applicable to all do problems that follow the same pattern, such as Subset Sum, etc.

Code

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
 {
  int t;cin>>t;
  while(t--){
      int numberOfItems;cin>>numberOfItems;
      int weightOfKnapsack;cin>>weightOfKnapsack;
      int wt[numberOfItems],val[numberOfItems]; // store the weight and value of each item
      
      //Taking input
      for(int i=0;i<numberOfItems;i++)
          cin>>val[i];
      for(int i=0;i<numberOfItems;i++)
          cin>>wt[i];
     
      //dp array to store the max value which can be achieved at any weight
      int dp[2][weightOfKnapsack+1];
      
      memset(dp,0,sizeof dp); //initialising the dp array to 0
      
      for(int i=0;i<numberOfItems;i++){
          for(int j=0;j<=weightOfKnapsack;j++){
              dp[i&1][j] = max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j] : 0));
              if(j>=wt[i])
                  dp[i&1][j] = max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j-wt[i]] : 0)+val[i]);
          }
      }
      
      cout<<dp[(numberOfItems-1)&1][weightOfKnapsack]<<endl;
  }
}

2

3 // number of items

4 // weight knapsack can hold

10 20 30 // value of items

4 5 1 // weight of items

3

3

10 2 3

4 50 60

30 
0

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
    	int t = sc.nextInt();
    	
    	while(t-- > 0){
    	    int numberOfItems = sc.nextInt();
    	    int weightOfKnapsack = sc.nextInt();
    	    
    	    // store the weight and value of each item
    	    int wt[] = new int[numberOfItems];
    	    int val[] = new int[numberOfItems]; 
    	    
    	    //Taking input
    	    for(int i=0;i<numberOfItems;i++)
    	        val[i] = sc.nextInt();
    	    for(int i=0;i<numberOfItems;i++)
    	        wt[i] = sc.nextInt();
    	   
    	    //dp array to store the max value which can be achieved at any weight
    	    int dp[][] = new int[2][weightOfKnapsack+1];
    	    
    	    //initialising the dp array to 0
    	    for(int i=0;i<2;i++) {
    	        for(int j=0;j<weightOfKnapsack+1;j++)
    	            dp[i][j] = 0;
    	    }
    	    
    	    for(int i=0;i<numberOfItems;i++){
    	        for(int j=0;j<=weightOfKnapsack;j++){
    	            dp[i&1][j] = Math.max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j] : 0));
    	            if(j>=wt[i])
    	                dp[i&1][j] = Math.max(dp[i&1][j], (i>=1 ? dp[(i-1)&1][j-wt[i]] : 0)+val[i]);
    	        }
    	    }
    	    
    	    System.out.println(dp[(numberOfItems-1)&1][weightOfKnapsack]);
    	}
    }
}

2

3 // number of items

4 // weight knapsack can hold

10 20 30 // value of items

4 5 1 // weight of items

3

3

10 2 3

4 50 60

30 
0

Complexity Analysis

Time Complexity: O(N*W)

where N = number of items

W = weight knapsack can hold

If N = W, time complexity = O(N^2)

Space Complexity: O(W)

where W = weight knapsack can hold, this is the reduced space complexity.