0-1 knapsack Bottom Up Dynamic Programming

0-1    knapsack Using Bottom Up Dynamic Programming-

Dp Tutorial -2

prerequisite

https://spoj-editorial1.blogspot.com/2020/07/0-1-knapsack-in-dynamic-programming.html

problem Statement-

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 solution-

Recursive=base condition+recursive call

Memorization=recursive call +table

Bottom up=table

 

Why we use Bottom Up dynamic programming?

In recursive solution there may cause a problem of stack overflow so avoid this problem we use bottom up technique.

How to solve-

In this dynamic programming tutorial we only focus to drive solution from previously tutorial.

now we have to convert

recursive +  memoization =>bottom Up

lets understand table-

eg.

Weight[]=[1,3,4,5]

Value=[1,4,5,7]

W=7

in left side from row 0 to 4-

row 0 means you have empty array

row 1-weight[]=[1], value[]=1

row 3-weight[]=[1,3,4] ,value[1,4,5]

This is why dynamic programming called technique of solving problem which can we divided into sub problem

 

How to fill table-

Step 1-Intialization

Step 2- convert Recursive call  to interation

Question Why we choose only n and W for table if you look recurve call from previous tutorial

Knapsack(int v[],int weight[],int n,int W) only n and W are changing so we choose n and W for Table.

 

Step 1-Initilization

We have to think about base condition

If(n==0||w==0)

  return 0;

so think about if you have array size of zero then for any weight size of knapsack value will be zero so we fill first row with zero.

Now think if you have zero weight size of knapsack then for any size of given array value will be zero so we fill first column with zero.

Step 2-Convert recursive call to iteration.

From previous tutorial

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

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

For these two=

if (weight[i-1]<=j)

dp[i][j]=max(value[i-1]+dp[i-1][j-weight[i-1]],dp[i-1][j])

//means if you choose this item then you have to choose previous but weight is decrease from current weight or if you don’t choose then previous row but column will not change because weight is not decrease.

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

For this

dp[i][j]=dp[i-1][j]

 

now fill Table

    0                     1                   2                      3                    4                     5                  6                    7

0	0	0	0	0	0	0	0
0	1	1	1	1	1	1	1
0	1	1	(4+0,1)	(4+1,1)	5	5	5
0	1	1	4	(5+0,5)	(5+1,5)	(5+1,5)	(5+4,5)
0	1	1	4	5	(7+0,6)	(7+1,6)	(7+1,9)

Answer will we dp[n][W] which is 9.

Where to Practice-

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

Code-

#include <bits/stdc++.h>

using namespace std;

int main() {

int t;

cin>>t;

while(t--)

{

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

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

   int dp[n+1][W+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];

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

   {

    for(int j=0;j<=W;j++)

    {

    if(i==0||j==0)

    dp[i][j]=0;

    else if(weight[i-1]<=j)

    dp[i][j]=max(value[i-1]+dp[i-1][j-weight[i-1]],dp[i-1][j]);

    else

    dp[i][j]=dp[i-1][j];

    }

   }

   cout<<dp[n][W]<<"\n";

}

}

Time complexity-

O(n*W)

Space complexity

(n*W)