0–1 Knapsack problem

Find the maximum profit which we get after including the elements whose sum of weights is less than or equal to the capacity of the knapsack

Example:

Input:  profit={3,4,5,2,6,7}, weight={1,3,4,2,5,8}, capacity=13
Output: 18   //i.e 3+4+5+6

Approach 1: Using recursion

Java

public class Knapsack01problem {
    public static void main(String[] args) {
        int[] profit = { 3, 4, 5, 2, 6, 7 };
        int[] weight = { 1, 3, 4, 2, 5, 8 };
        int capacity = 13;

        System.out.println(knapSack(profit, weight, capacity, profit.length - 1));
    }

    // function to find the maximum profit
    // we can get after putting all elements whose
    // capacity of weight is less then or equal to capacity
    static int knapSack(int[] profit, int[] weight, int capacity, int n) {

        // base case if their is no elements
        // or capacity is zero then return 0
        if (n == -1 || capacity == 0)
            return 0;

        // if the weight of current element is
        // greater than the value of the remaining
        // capacity then ignore the current element
        if (weight[n] > capacity)
            return knapSack(profit, weight, capacity, n - 1);

        // else the answer will we max after including
        // the current element or by excluding the current element
        else
            return Math.max(knapSack(profit, weight, capacity, n - 1),
                    profit[n] + knapSack(profit, weight, capacity -
                         weight[n], n - 1));
    }
}

C++

#include <bits/stdc++.h>
using namespace std;


//function to find the maximum profit 
//we can get after putting all elements whose
//capacity of weight is less then or equal to capacity
int knapSack(vector<int> profit,vector<int> weight,int capacity,int n)
{

    //base case if their is no elements
    //or capacity is zero then return 0
    if(n==-1||capacity==0)
       return 0;

    //if the weight of current element is 
    //greater than the value of the remaining 
    //capacity then ignore the current element
    if(weight[n]>capacity)
       return knapSack(profit,weight,capacity,n-1);

    //else the answer will we max after including
    //the current element or by excluding the current element
    else
      return max(knapSack(profit,weight,capacity,n-1),
          profit[n]+knapSack(profit,weight,capacity-weight[n],n-1));
}
int main()
{
    vector<int> profit={3,4,5,2,6,7};
    vector<int> weight={1,3,4,2,5,8};
    int capacity=13;

    cout<<knapSack(profit,weight,capacity,profit.size()-1);

    return 0;
    
}

Approach 2: Using memoization dynamic programming

Java

public class Knapsack01problem1 {
    public static void main(String[] args) {
        int[] profit = { 3, 4, 5, 2, 6, 7 };
        int[] weight = { 1, 3, 4, 2, 5, 8 };
        int capacity = 13;
        dp = new int[100][100];
        System.out.println(knapSackDP(profit, weight, capacity,
             profit.length - 1));
    }

    static int dp[][];

//function to find the maximum profit 
//we can get after putting all elements whose
//capacity of weight is less then or equal to capacity
    static int knapSackDP(int[] profit, int[] weight, int capacity, int n) {

        // base case if their is no elements
        // or capacity is zero then return 0
        if (n == -1 || capacity == 0)
            return 0;

        // if already calculated then return
        if (dp[n][capacity] != 0)
            return dp[n][capacity];
        // if the weight of current element is
        // greater than the value of the remaining
        // capacity then ignore the current element
        if (weight[n] > capacity)
            dp[n][capacity] = knapSackDP(profit, weight, capacity, n - 1);

        // else the answer will we max after including
        // the current element or by excluding the current element
        else
            dp[n][capacity] = Math.max(knapSackDP(profit, weight, capacity, n - 1),
            profit[n] + knapSackDP(profit, weight, capacity - weight[n], n - 1));
        return dp[n][capacity];
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int dp[100][100];
//function to find the maximum profit 
//we can get after putting all elements whose
//capacity of weight is less then or equal to capacity
int knapSackDP(vector<int> profit,vector<int> weight,int capacity,int n)
{

    //base case if their is no elements
    //or capacity is zero then return 0
    if(n==-1||capacity==0)
       return 0;

   //if already calculated then return 
    if(dp[n][capacity]!=-1)
        return dp[n][capacity];
    //if the weight of current element is 
    //greater than the value of the remaining 
    //capacity then ignore the current element
    if(weight[n]>capacity)
       dp[n][capacity]=knapSackDP(profit,weight,capacity,n-1);

    //else the answer will we max after including
    //the current element or by excluding the current element
    else
      dp[n][capacity]=max(knapSackDP(profit,weight,capacity,n-1),
        profit[n]+knapSackDP(profit,weight,capacity-weight[n],n-1));
    return dp[n][capacity];
}
int main()
{
    vector<int> profit={3,4,5,2,6,7};
    vector<int> weight={1,3,4,2,5,8};
    int capacity=13;
    memset(dp,-1,sizeof(dp));
    cout<<knapSackDP(profit,weight,capacity,profit.size()-1);

    return 0;
    
}