01Knapsack by Top Down Approach

 import java.util.Scanner;

import java.util.*;

class KnapsackImplementation{

int[][] t;

int opt;

int n;

int k;

public KnapsackImplementation(int k,int n){

this.n=n;

this.k=k;

opt=0;

this.t=new int[n+1][k+1];

}   

public int knapsack(int w[],int val[], int k,int n){

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

for(int j=0;j<k+1;j++){

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

t[i][j]=0;

}

}

} 

for(int i=1;i<n+1;i++){

for(int j=1;j<k+1;j++){

if(w[i-1]>j){

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

}

else{

t[i][j]=Integer.max((val[i-1]+t[i-1][j-w[i-1]]),t[i-1][j]);

}

}

}

return t[n][k];

}

}

class O1KnapsackbyTopDown{

public static void main(String arg[]){

Scanner sc=new Scanner(System.in);

int n=sc.nextInt();

int w[]=new int[n];

int val[]=new int[n];

System.out.println("enter elements of weight array.");

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

w[i]=sc.nextInt();

}

System.out.println("enter elements of value array.");

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

val[i]=sc.nextInt();

}

System.out.println("Enter the weight of knapsack");

int k=sc.nextInt();

KnapsackImplementation obj=new KnapsackImplementation(k,w.length);

int b=obj.knapsack(w,val,k,w.length);

System.out.println(b);

}

}

Approach: Here we will see that if any element belongs to either the first row or first column then we will initialize the cell with 0. It is so because for the first row ie index 0 row it means that no element in the weight array and similarly for k=0 no weight of knapsack (which were base conditions in recursive solution.)

Then we will traverse the 2d array starting from index 1 (both rows and columns) and see whether the weight of the item is more than the weight of the knapsack or not. If yes then either include it in a knapsack or not (which condition will give us maximum profit) and if no then we will leave that element of weight array and traverse furhter.

Here we will have to return the value of maximum profit which is the last index of the 2d matrix ie matrix t.[t[n][k]]

Moreover here we are filling the value of cells by taking the help of values of other previously filled cells. As we traverse further it means earlier cells are filled up and we are using their values to calculate the value of the next cells.

TIME: O(N*K) [2 loops]

SPACE: O(N*K) [2D ARRAY]

Thanks for Reading.😇