0-1 Knapsack Geeks for Geeks Solution
BY RECURSION:
Geeks For Geeks*******************************************************************
class Solve{
public int knapsack(int w, int[] arr, int[] val, int n){
if(n==0 || w==0){
return 0;
}
else{
if(arr[n-1]>w){
return knapsack(w,arr,val,n-1);
}
else{
return Integer.max(knapsack(w,arr,val,n-1),val[n-1]+knapsack(w-arr[n-1],arr,val,n-1));
}
}
}
}
class Solution
{
//Function to return max value that can be put in the knapsack of capacity W.
static int knapSack(int w, int wt[], int val[], int n)
{
Solve obj1=new Solve();
int c=obj1.knapsack(w,wt,val,n);
return c;
}
}
It will display Time Limit Exceeded Error.
-----------------------------------------------------------------------------------------------------------------------------
BY MEMOIZATION
Geeks for Geeks
*************************************************************************
class Solution
{
//Function to return max value that can be put in the knapsack of capacity W.
static int knapSack(int w, int arr[], int val[], int n)
{
int t[][]=new int[n+1][w+1];
if(n==0 || w==0){
return 0;
}
for(int i=0;i<n+1;i++){
for(int j=0;j<w+1;j++){
t[i][j]=-1;
}
}
if(t[n][w]!=-1){
return t[n][w];
}
else{
if(arr[n-1]>w){
t[n][w]= knapSack(w,arr,val,n-1);
}
else{
t[n][w]=Integer.max(knapSack(w,arr,val,n-1),val[n-1]+knapSack(w-arr[n-1],arr,val,n-1));
}
return t[n][w];
}
}
}
--------------------------------------------------------------------------------------------------------------------------
BY TOP-DOWN APPROACH:
class Solution
{
//Function to return max value that can be put in knapsack of capacity W.
static int knapSack(int w, int arr[], int val[], int n)
{
int t[][]=new int[n+1][w+1];
if(n==0 || w==0){
return 0;
}
for(int i=0;i<n+1;i++){
for(int j=0;j<w+1;j++){
if(i==0)
t[i][j]=0;
if(j==0)
t[i][j]=0;
}
}
for(int i=01;i<n+1;i++){
for(int j=01;j<w+1;j++){
if(arr[i-1]>j){
t[i][j]= t[i-1][j];
}
else{
t[i][j]=Integer.max(t[i-1][j],val[i-1]+t[i-1][j-arr[i-1]]);
}
}
}
return t[n][w];
}
}
REASON OF ACCEPTANCE OF TOP-DOWN APPROACH ONLY
In Recursion: Recursive Calls [Time is :a]
In Memorization: Recursive Calls + 2D matrix [Time is:b]
In Top-Down: Only 2D Matrix [Time is: c]
And the result is a>b>c
Recursive calls are piled up in a stack, and they are returned when their result is calculated simultaneously, which takes more time than storing results in a 2d matrix.
In memoization, we store results in a matrix simultaneously but we do have recursive calls.[here we get the answer from the matrix but if that cell has value -1 it means the subproblem is not solved yet then we go for the recursive call.]
While top-down is free of recursive calls. Moreover, it fills the matrix on the previously calculated results of subproblem which is far easier and less time-consuming than calling the same function repeatedly.
That's why the Top-down approach got selected rather than recursive and memoization.
Thanks for Reading.😇
Comments
Post a Comment