如何最佳地将数组划分为两个子数组，使两个子数组中的元素总和相同，否则会出错?

问题描述

如何将一个数组最优地划分为两个子数组，使两个子数组中的元素之和相同，否则报错?

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

}

//贪心方法//

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