如何将一个数组最佳地划分为两个子数组，以使两个元素的总和相同，否则会出现错误？ [英] How to optimally divide an array into two subarrays so that sum of elements in both are same, otherwise give an error?

问题描述

如何最佳地将一个数组分为两个子数组，以使两个子数组中的元素之和相同，否则会出现错误？

How to optimally divide an array into two subarrays so that sum of elements in both subarrays is same, otherwise give an error?

给出数组

10,  20 , 30 , 5 , 40 , 50 , 40 , 15

可以分为

10, 20, 30, 5, 40

和

50, 40, 15

每个子数组的总和为105。

Each subarray sums up to 105.

10,  20,  30,  5,  40,  50,  40,  10

数组不能分为两个相等的数组。

The array cannot be divided into 2 arrays of an equal sum.

推荐答案

public class Problem1 {

public static void main(String[] args) throws IOException{
    Scanner scanner=new Scanner(System.in);
    ArrayList<Integer> array=new ArrayList<Integer>();
    int cases;
    System.out.println("Enter the test cases");
    cases=scanner.nextInt();

    for(int i=0;i<cases;i++){
        int size;


        size=scanner.nextInt();
        System.out.println("Enter the Initial array size : ");

        for(int j=0;j<size;j++){
            System.out.println("Enter elements in the array");
            int element;
            element=scanner.nextInt();
            array.add(element);
        }
    }

    if(validate(array)){
System.out.println("Array can be Partitioned");}
  else{
     System.out.println("Error");}

}

public static boolean validate(ArrayList<Integer> array){
    boolean flag=false;
    Collections.sort(array);
    System.out.println(array);
    int index=array.size();

    ArrayList<Integer> sub1=new ArrayList<Integer>();
    ArrayList<Integer> sub2=new ArrayList<Integer>();

    sub1.add(array.get(index-1));
    array.remove(index-1);

    index=array.size();
    sub2.add(array.get(index-1));
    array.remove(index-1);

    while(!array.isEmpty()){

    if(compareSum(sub1,sub2)){
        index=array.size();
        sub2.add(array.get(index-1));
        array.remove(index-1);
    }
    else{
        index=array.size();
        sub1.add(array.get(index-1));
        array.remove(index-1);
    }   
    }

    if(sumOfArray(sub1).equals(sumOfArray(sub2)))
        flag=true;
    else
        flag=false;

    return flag;
}

public static Integer sumOfArray(ArrayList<Integer> array){
    Iterator<Integer> it=array.iterator();
    Integer sum=0;
    while(it.hasNext()){
        sum +=it.next();
    }

    return sum;
}

public static boolean compareSum(ArrayList<Integer> sub1,ArrayList<Integer> sub2){
    boolean flag=false;

    int sum1=sumOfArray(sub1);
    int sum2=sumOfArray(sub2);

    if(sum1>sum2)
        flag=true;
    else
        flag=false;

    return flag;
}

}

//贪婪的方法//

// The Greedy approach //

这篇关于如何将一个数组最佳地划分为两个子数组，以使两个元素的总和相同，否则会出现错误？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！