Equal Sum Partition Memoize Approach
import java.util.Scanner;
class KnapsackSolve{
public int knapsack(int[] arr, int n, int sum){
int t[][]=new int[n+1][sum+1];
for(int i=0;i<n+1;i++){
for(int j=0;j<sum+1;j++){
t[i][j]=-1;
}
}
if(n==0 && sum==0){
return 1;
}
if(n==0 && sum!=0){
return 0;
}
if(sum==0){
return 1;
}
if(t[n][sum]!=-1){
return t[n][sum];
}
else{
if(arr[n-1]>sum){
t[n][sum]=knapsack(arr,n-1,sum);
}
else{
t[n][sum]=Integer.max(knapsack(arr,n-1,sum),knapsack(arr,n-1,sum-arr[n-1]));
}
return t[n][sum];
}
}
}
class EqualSumPartitionMemoize{
public static void main(String arg[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
int sum=0;
for(int i=0;i<n;i++){
sum=sum+arr[i];
}
if(sum%2!=0){
System.out.println("false");
System.out.println("Not possible");
}
else{
KnapsackSolve obj1=new KnapsackSolve();
int c=obj1.knapsack(arr,n,sum/2);
System.out.println(c);
}
}
}
Comments
Post a Comment