Problem Description

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don’t pick it (0-1 property).

Problem Link

0 - 1 Knapsack Problem | Practice | GeeksforGeeks

Recursive Approach

int knapSack(int W, int wt[], int val[], int n)
{
 
    // Base Case
    if (n == 0 || W == 0)
        return 0;
 
    // If weight of the nth item is more
    // than Knapsack capacity W, then
    // this item cannot be included
    // in the optimal solution
    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);
 
    // Return the maximum of two cases:
    // (1) nth item included
    // (2) not included
    else
        return max(
            val[n - 1]
                + knapSack(W - wt[n - 1],
                           wt, val, n - 1),
            knapSack(W, wt, val, n - 1));
}

Memorization (Top Down DP)

/* In this approach we just store the value of each recursive call in a lookup table 
(which is initialized with -1). The lookup table is usually declared globally using 
the constraints given in the problem.  */

int lookup[102][1002]; //n<=100, W<=1000
int knapSack(int W, int wt[], int val[], int n)
{
    //Initializing the lookup table
    for(int i=0;i<=n;i++)
    {
      for(int j=0;j<=W;j++)
       lookup[i][j] = -1;
    }
  return knapSackRecur(W,wt,val,n);
}
int knapSackRecur(int W, int wt[], int val[], int n)
{
 
    // Base Case
    if (n == 0 || W == 0)
        return 0;
    //If value already calculated then just return its value
    if(lookup[n][W]!=-1)
        return lookup[n][W];
    // If weight of the nth item is more
    // than Knapsack capacity W, then
    // this item cannot be included
    // in the optimal solution
    if (wt[n - 1] > W)
        return lookup[n][W] = knapSackRecur(W, wt, val, n - 1);
 
    // Return the maximum of two cases:
    // (1) nth item included
    // (2) not included
    else
        return lookup[n][W] = max(
            val[n - 1]
                + knapSackRecur(W - wt[n - 1],
                           wt, val, n - 1),
            knapSackRecur(W, wt, val, n - 1));
}

Iterative approach (Bottom Up DP)

// Returns the maximum value that
// can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
    int i, w;
    int K[n + 1][W + 1];
 
    // Build table K[][] in bottom up manner
    for(i = 0; i <= n; i++)
    {
        for(w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1] +
                                K[i - 1][w - wt[i - 1]],
                                K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }
    return K[n][W];
}

Complexity Analysis:

• Time Complexity: O(N*W). As redundant calculations of states are avoided.
• Auxiliary Space: O(N*W). The use of 2D array data structure for storing intermediate states-

Space Optimized Approach

// Time Complexity : O(n^2)
// Space Complexity : O(n)
// Just swap the places of bolded 0 and 1 and it will convert into unbounded KS
class Solution
{
    public:
    //Function to return max value that can be put in knapsack of capacity W.
    int knapSack(int W, int wt[], int val[], int N) 
    { 
       vector<vector<int>> dp(2,vector<int>(W+1,0));
        
        for(int i=0;i<N;i++)
        {
            int j = 1;
            
            if(i%2==0) //currently we have odd number of elements
            {
               while(j<=W) // j = current capacity of the bag
               {
                   if(j>=wt[i])
                   dp[0][j] = max(dp[**1**][j-wt[i]]+val[i],dp[1][j]);
                   
                   else
                   dp[0][j] = dp[1][j];
                   
                   j++;
               }
            }
            else //currently we have even number of elements
            {
                 while(j<=W)
                 {
                   if(j>=wt[i])
                   dp[1][j] = max(dp[**0**][j-wt[i]]+val[i],dp[0][j]);
                   
                   else
                   dp[1][j] = dp[0][j];
                   
                   j++;
                 }
            }
            
        }
        
        return N%2 ? dp[0][W] : dp[1][W];
    }
};