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)
No comments:
Post a Comment