0-1 knapsack in Dynamic Programming

DP Tutorial 1-
0-1            Knapsack dynamic programming-

Problem Explanation-

you are given a weight array and respective value array and maximum size of knapsack and you have to put these item in such a way so that you will get maximum total value in knapsack.

 

Type of knapsack problem

1.Fractional Knapsack-

This type of problem lie under the category of greedy .For more details -https://www.geeksforgeeks.org/fractional-knapsack-problem/

2.0-1 knapsack

This is a dp based problem.As 1 means you take this item in knapsack 0 means you didn’t take this item in knapsack.

3.Unbounded knapsack

The difference between 0-1 and unbounded knapsack is that you have infinity supply of each item.

 

How to identify Dynamic Programming-

From tutorial 0 we know that you have to find two things

1.Choice-

As in  this problem you can take item or not .

2.Optimal-

Means maximum or minimum and here you have to find maximum profit.

Choice Diagram- I recommend you to always make choice diagram this will help you to visualize and writing recursion.

 

Solution Using Recursion-

Function()

{

    Base condition;

     Choice diagram;
}

 

How to think about base condition?

Think about smallest valid input.

1.Array size can be zero

2.Size of knapsack can be zero

So base condition

If(n==0||W==0)

 return 0;

 

Code for choice diagram

 

Taken then=> value[n-1]+knapsack(value[],weight[],n-1,W-weight[n-1])

Not Taken=>knapsack(value[],weight[],n-1,W)

Size greater =>knapsack(value[],weight[],n-1,W)

 

Code-

 int knapsack(int value[],int weight[],int n,int W)

{

if(n==0||W==0)

return 0;

if(weight[n-1]<=W)

return max(value[n-1]+knapsack(value,weight,n-1,W-weight[n-1]),

knapsack(value,weight,n-1,W));

else

return knapsack(value,weight,n-1,W);

}

Solution Using Memoization-

In memorization or bottom up to avoid recalculation we saved the calculation in a array .

But what is the size of array ?

We simply convert recursion recurrence relation to memorization

What value change

1.n and 2.W (size of Knapsack)

Now array will be dp[n][W]

We initially filled array to -1 to check it if here in this point calculation is done or not;

Code-

int knapsack(int value[],int weight[],int n,int W)

{   if(dp[n][W]!=-1)

       return dp[n][W];

if(n==0||W==0)

return 0;

if(weight[n-1]<=W)

return dp[n][W]=max(value[n-1]+knapsack(value,weight,n-1,W-weight[n-1]),

knapsack(value,weight,n-1,W));

else

return dp[n][W]=knapsack(value,weight,n-1,W);

}

 

Child Problems-

1.subset sum

2.Equal Sum Partition

3.Count of Subset sum

4.minimum Subset sum Difference

5.Target Sum

6.No. of subset equal to given difference

 

Where to Practice-

https://practice.geeksforgeeks.org/problems/0-1-knapsack-problem/0

 

Code for above problem (complete code)

#include <bits/stdc++.h>

using namespace std;

int dp[1001][1001];

int knapsack(int value[],int weight[],int n,int W)

{   if(dp[n][W]!=-1)

       return dp[n][W];

if(n==0||W==0)

return 0;

if(weight[n-1]<=W)

return dp[n][W]=max(value[n-1]+knapsack(value,weight,n-1,W-weight[n-1]),

knapsack(value,weight,n-1,W));

else

return dp[n][W]=knapsack(value,weight,n-1,W);

}

int main() {

int t;

cin>>t;

while(t--)

{

    int n,W;cin>>n>>W;

    int value[n+1],weight[n+1];

    memset(dp,-1,sizeof(dp));

    for(int i=0;i<n;i++)

     cin>>value[i];

    

    for(int i=0;i<n;i++)

      cin>>weight[i];

    cout<<knapsack(value,weight,n,W)<<"\n";

}

}