如何最佳地将数组划分为两个子数组，使两个子数组中的元素总和相同，否则会出错? [英] 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

数组不能被分成相等和的2个数组.

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;
}

}

//贪心方法//

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