01 Knapsack Problem by Memiozation

 import java.util.Scanner;

import java.util.*;

class KnapsackImplementation{

static 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];

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

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

t[i][j] = -1;   

  }

}

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

 

if(n==0 || k==0){

opt=0;

return 0;

}

if(t[n][k]!=-1){

opt=t[n][k];

System.out.println("Element existing  is: "+t[n][k]);

return t[n][k];

}

else {

if(w[n-1]<=k){

System.out.println("Weight is less.");

System.out.println("NOw we have choice wither to include or not.");

t[n][k]=Integer.max((val[n-1]+knapsack(w,val,k-w[n-1],n-1)),(knapsack(w,val,k,n-1)));

System.out.println("Element max is: "+t[n][k]);

return t[n][k];

}

else{

System.out.println("Weight of last element is more. NOt to be included.");

t[n][k]=knapsack(w,val,k,n-1);

System.out.println("Element with more weight is: "+t[n][k]);

return t[n][k];

}

}

}

}

class O1KnapsackbyMemiozation{

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 first find out the recursive solution.

Then we will do memoization. The idea is we will start iterating the array from the end and picking one element, we will see if the value of the element is more than the weight of the knapsack, then we will have a choice of either including it in the knapsack or not. Now we will find out the maximum value between two cases of either including element or not. And if the weight of an element is more than capacity then it will not be included.

In this way, we will traverse the array and reach at the end where the base condition is the size of the weight array becomes 0(ie all the elements get included) or the weight constraint is full(the capacity of the knapsack is full).

Time:O(N*W)

Space: O(N*W) Array 2d is used.

Thanks for Reading.😇