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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

例子1

给定数组

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

它可以分为

10, 20, 30, 5, 40

和

50, 40, 15

每个子数组的总和为105。

例子2

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

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

回答：

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

//贪婪的方法//

以上是 如何将一个数组最佳地划分为两个子数组，以使两个元素的总和相同，否则会出现错误？ 的全部内容， 来源链接： utcz.com/qa/406077.html

回到顶部