01 Knapsack By Recursion
import java.util.Scanner;
class KnapsackSolve{
public int knapsack(int[] arr, int n, int W , int[] val){
if(n==0 || W==0){
return 0;
}
else{
if(arr[n-1]>W){
return knapsack(arr,n-1,W,val);
}
else{
return Integer.max((val[n-1]+knapsack(arr,n-1,W-arr[n-1],val)),(knapsack(arr,n-1,W,val)));
}
}
}
}
class O1KnapsackRecursion{
public static void main(String arg[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[]=new int[n];
int val[]=new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
for(int i=0;i<n;i++){
val[i]=sc.nextInt();
}
int W=sc.nextInt();
KnapsackSolve obj1=new KnapsackSolve();
int c=obj1.knapsack(arr,n,W,val);
System.out.println(c);
}
}
Time:O(N*W)
Space:O(N*W)
Comments
Post a Comment