如何最优地将数组划分为两个子数组,以使两者中的元素总和相同,否则会出错？

Question

如何最优地将数组划分为两个子数组,以使两个子数组中的元素总和相同,否则会出错？

例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

该数组不能分为2个等数和的数组.

Answer 1

存在一种涉及动态编程的解决方案,其运行于O(n*TotalSum),其中n是数组中元素的数量,并且TotalSum是它们的总和.

第一部分包括计算可以通过向数组添加元素来创建的所有数字的集合.

对于一个大小的数组n,我们将称之为T(n),

T(n) = T(n-1) UNION { Array[n]+k | k is in T(n-1) }

(正确性的证明是通过归纳,就像大多数递归函数一样.)

另外,请记住动态矩阵中的每个单元格,为了创建它而添加的元素.

简单的复杂性分析将表明这是完成的O(n*TotalSum).

计算完成后T(n),在集合中搜索完全相同大小的元素TotalSum / 2.

如果这样的项存在,则创建它的元素,加在一起,相等TotalSum / 2,并且不属于其创建的元素也等于TotalSum / 2(TotalSum - TotalSum / 2 = TotalSum / 2).

这是伪多项式解.AFAIK,这个问题不知道在P中.

Answer 2

这称为分区问题.对于某些特殊情况,有最佳解决方案.但是,一般来说,这是NP完全问题.

Answer 3

在其常见变体中，此问题强加了 2 个约束，并且可以以更简单的方式完成。

1. 如果分区只能在数组长度的某处完成（我们不考虑元素乱序）
2. 没有负数。

然后工作的算法可能是：

1. 有 2 个变量，leftSum 和 rightSum
2. 从数组的左侧开始增加 leftSum，从右侧开始增加 rightSum。
3. 尝试纠正其中的任何不平衡。

以下代码执行上述操作：

public boolean canBalance(int[] nums) {
  int leftSum = 0, rightSum = 0, i, j;
  if(nums.length == 1)
      return false;
  for(i=0, j=nums.length-1; i<=j ;){
      if(leftSum <= rightSum){
         leftSum+=nums[i];
         i++;
      }else{
         rightSum+=nums[j];
         j--;
      }
  }
  return (rightSum == leftSum);
}

输出：

canBalance({1, 1, 1, 2, 1})       ? true    OK      
canBalance({2, 1, 1, 2, 1})       ? false   OK      
canBalance({10, 10})              ? true    OK          
canBalance({1, 1, 1, 1, 4})       ? true    OK      
canBalance({2, 1, 1, 1, 4})       ? false   OK      
canBalance({2, 3, 4, 1, 2})       ? false   OK      
canBalance({1, 2, 3, 1, 0, 2, 3}) ? true    OK      
canBalance({1, 2, 3, 1, 0, 1, 3}) ? false   OK      
canBalance({1})                   ? false   OK      
canBalance({1, 1, 1, 2, 1})       ? true    OK

当然，如果元素可以乱序组合，它确实会变成具有所有复杂性的分区问题。

Answer 4

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

}

// 贪婪方法 //