The Knapsack Problem - solve the Knapsack Problem with dp

Before going to “The Knapsack Problem” first look at a real-life problem. Sakshi wants to carry away the maximum vegetables from a garden. However, her sack has a maximum weight capacity and might break on the addition of extra weight.

Let’s look into the situation-

Items: {Potato, Tomato, Ginger, Garlic, Okra }
Weights: {2,3,1,4,6}
Profits: {4,5,3,7,8}
KnapSack Capacity: 7

We thus have to find a way such that Sakshi gets the maximum profits out of the veggies without breaking the sack.

Table of Contents

Brute Force Approach for The Knapsack Problem

We have the following approach while doing so

Considering all the possible sets of items
Calculating the total weight and value of all of them
Picking out the subset with the maximum value that does not exceed the weight limit.

While considering so:

We have two choices for each nth item

We can put it into the Knapsack(1):

Value of the sack=Maximum value obtained from n-1 items

We cannot put it into the KnapSack(0):

Value of the sack=Maximum value obtained from n-1 items+Value of our nth item where the capacity of the bag would now shrink to capacity-weight of nth item.

If the weight of an item is greater than the capacity of the KnapSack it cannot be included and we would have to look into the rest of the items we have with us.

Let’s look into the implementation of the same:

Java Program

import java.util.*;
public class knaprec
{
  public static int knaprec(int max,int w[],int val[],int n)
  {
    if(n==0 || max==0)
      return 0;
    else if(w[n-1]>=max)
      return knaprec(max,w,val,n-1);
    else
      return(Math.max(w[n-1]+knaprec(max-w[n-1],w,val,n-1),knaprec(max,w,val,n-1)));
  }
  public static void main(String args[])
  {
    int n=5;
    int max=10;
    int w[]=new int[]{12,1,2,1,4};
    int val[]=new int[]{4,1,2,2,10};
    int ans=knaprec(max,w,val,n);
    System.out.println(ans);
  }
}

C++ Code

#include<iostream> 
int maxs(int a,int b)
{
        if(a>b)
            return a;
        else
            return b;
}
int knaprec(int max,int w[],int val[],int n)
{ 
        if(n==0 || max==0) 
            return 0; 
        else if(w[n-1]>=max) 
            return knaprec(max,w,val,n-1); 
        else 
            return(maxs(w[n-1]+knaprec(max-w[n-1],w,val,n-1),knaprec(max,w,val,n-1))); 
} 
int main() 
{ 
        int n=5; 
        int max=10; 
        int w[]={12,1,2,1,4}; 
        int val[]={4,1,2,2,10}; 
        int ans=knaprec(max,w,val,n); 
        cout<<ans; 
}

Explanation for The Knapsack Problem

Let’s look into the calls made by our program for

Weights:{10, 2, 3,5}

Values:{100, 70, 50,40}

Maximum capacity of the KnapSack: 15kg.

The Knapsack Problem

We see multiple calls being made to (1,10) which becomes worse as work with bigger test cases involving more weights and values. Such a solution needs a lot of time as well and has a time complexity of O(n^2)

How can we improve?

We are supposed to not solve the same problem again and again. How can we do that? By storing the results in an auxiliary array/table from where they can be accessed.

Java Program for The Knapsack Problem

import java.util.*;
class knap
{
  public static int KnapSack(int max,int w[],int val[],int n)
  {
    int dp[][]=new int[n+1][max+1];
    for(int i=0;i<=n;i++)
    {
      for(int j=0;j<=max;j++)
      {
        if(i==0 || j==0)
          dp[i][j]=0;
        //The KnapSack cannot have any value if there are no objects added.
        else if(w[i-1]<=j)
        {
          //val[j]=Value of the current weight
          //dp[i-1][j-w[i-1]]=The value of the KnapSack when previous weight was added
          //val[j]+dp[i-1][j-w[i-1]]=The value of the KnapSack in case we add the current weight
          //dp[i-1][j]=The value of the KnapSack without the current weight
          dp[i][j]=Math.max(val[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]);
        }
        else
          dp[i][j]=dp[i-1][j];
      }
    }
    return dp[n][max];
  }
  public static void main(String args[])
  {
    Scanner sc=new Scanner(System.in);
    int n=5;
    int max=4;
    int w[]=new int[]{12,1,2,1,4};
    int val[]=new int[]{4,1,2,2,10};
    int ans=KnapSack(max,w,val,n);
    System.out.println(ans);
  }
}

C++ Program

#include<iostream>
using namespace std;
int maxs(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
int KnapSack(int max,int w[],int val[],int n) 
{ 
    int dp[n+1][max+1]; 
    for(int i=0;i<=n;i++) 
    { 
    for(int j=0;j<=max;j++) 
    { 
     if(i==0 || j==0)
         dp[i][j]=0; 
     //The KnapSack cannot have any value if there are no objects added. 
     else if(w[i-1]<=j) 
     { 
      //val[j]=Value of the current weight 
      //dp[i-1][j-w[i-1]]=The value of the KnapSack when previous weight was added 
      //val[j]+dp[i-1][j-w[i-1]]=The value of the KnapSack in case we add the current weight           //dp[i-1][j]=The value of the KnapSack without the current weight 
         dp[i][j]=maxs(val[i-1]+dp[i-1][j-w[i-1]],dp[i-1][j]); 
     } 
     else 
         dp[i][j]=dp[i-1][j]; 
    } 
    }
    return dp[n][max]; 
}
int main() 
{ 
    int n=5; 
    int max=4; 
    int w[]={12,1,2,1,4}; 
    int val[]={4,1,2,2,10}; 
    int ans=KnapSack(max,w,val,n); 
    cout<<ans; 
}

Complexity Analysis for The Knapsack Problem

Voila, the time complexity now reduces to O(n*max) where n=no. of items and max=maximum weight our knapsack can hold.

References