如何将一组数字分成两组，使它们之和的差最小

Question

如何编写 Java 程序将一组数字分成两组，使它们各自数字之和的差值最小。

例如，我有一个包含整数的数组 - [5,4,8,2]。我可以将它分成两个数组 - [8,2] 和 [5,4]。假设给定的一组数字，可以像上面的例子一样有一个唯一的解决方案，如何编写一个 Java 程序来实现解决方案。即使我能够找出最小可能的差异也没关系。假设我的方法接收一个数组作为参数。该方法必须先将接收到的数组分成两个数组，然后将它们包含的整数相加。此后，它必须 return 它们之间的差异，以使差异尽可能小。

P.S.- 我在这里四处看看，但找不到任何具体的解决方案。此处似乎给出了最可能的解决方案- divide an array into two sets with minimal difference 。但是我无法从该线程中收集到如何编写 Java 程序来明确解决问题。

编辑：

看了@Alexandru Severin 的评论后，我尝试了一个java程序。它适用于一组数字 [1,3,5,9]，但不适用于另一组数字 [4,3,5,9,11]。下面是程序。请提出更改建议：-

 import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindMinimumDifference {
public static void main(String[] args) {
    int[] arr= new int[]{4,3,5,9, 11};  
    FindMinimumDifference obj= new FindMinimumDifference();
    obj.returnMinDiff(arr);
}

private int  returnMinDiff(int[] array){


    int diff=-1;
    Arrays.sort(array);
    List<Integer> list1= new ArrayList<>();
    List<Integer> list2= new ArrayList<>();
    int sumOfList1=0;
    int sumOfList2=0;
    for(int a:array){
        for(Integer i:list1){
            sumOfList1+=i;
        }
        for(Integer i:list2){
            sumOfList2+=i;
        }
        if(sumOfList1<=sumOfList2){
        list1.add(a);
        }else{
            list2.add(a);
        }
    }

    List<Integer> list3=new ArrayList<>(list1);   
    List<Integer> list4= new ArrayList<>(list2);   
    Map<Integer, List<Integer>> mapOfProbables= new HashMap<Integer, List<Integer>>();
    int probableValueCount=0;
    for(int i=0; i<list1.size();i++){  
        for(int j=0; j<list2.size();j++){
            if(abs(list1.get(i)-list2.get(j))<
abs(getSumOfEntries(list1)-getSumOfEntries(list2))){
                List<Integer> list= new ArrayList<>();
                list.add(list1.get(i));
                list.add(list2.get(j));    
                mapOfProbables.put(probableValueCount++, list);
            }
        }
    }
    int minimumDiff=abs(getSumOfEntries(list1)-getSumOfEntries(list2));
    List resultList= new ArrayList<>();
    for(List probableList:mapOfProbables.values()){  
        list3.remove(probableList.get(0));
        list4.remove(probableList.get(1));
        list3.add((Integer)probableList.get(1));
        list4.add((Integer)probableList.get(0));
        if(minimumDiff>abs(getSumOfEntries(list3)-getSumOfEntries(list4))){ 
// valid exchange 
                minimumDiff=abs(getSumOfEntries(list3)-getSumOfEntries(list4));
                resultList=probableList;
        }

    }

    System.out.println(minimumDiff);

    if(resultList.size()>0){
        list1.remove(resultList.get(0));
        list2.remove(resultList.get(1));
        list1.add((Integer)resultList.get(1));
        list2.add((Integer)resultList.get(0));
    }

    System.out.println(list1+""+list2);  // the two resulting set of 
// numbers with modified data giving expected result

    return minimumDiff;
}

private static int getSumOfEntries(List<Integer> list){
    int sum=0;
    for(Integer i:list){
        sum+=i;
    }
    return sum;
}
private static int abs(int i){
    if(i<=0) 
        i=-i;
    return i;
}
}

Answer 1

这是分区问题的变体https://en.wikipedia.org/wiki/Partition_problem

如果您想要最佳解决方案，则必须测试每一种可能的输出集组合。这对于小集合可能是可行的，但对于大输入是不可行的。

一个很好的近似是我在下面介绍的贪心算法。

This heuristic works well in practice when the numbers in the set are of about the same size as its cardinality or less, but it is not guaranteed to produce the best possible partition.

首先，您需要将输入放入一个可排序的集合中，例如列表。

1) 对输入集合进行排序。

2) 创建 2 个结果集。

3) 迭代排序的输入。如果索引甚至将项目放入 result1，否则将项目放入 result2。

  List<Integer> input = new ArrayList<Integer>();
  Collections.sort(input);
  Set<Integer> result1 = new HashSet<Integer>();
  Set<Integer> result2 = new HashSet<Integer>();
  for (int i = 0; i < input.size(); i++) {
      if (i % 2 == 0) {// if i is even
          result1.add(input.get(i));
      } else {
          result2.add(input.get(i));
      }
  }

Answer 2

看来你对算法比对代码更感兴趣。所以，这是我的伪代码：-

int A[];//This contains your elements in sorted (descending) order
int a1[],a2[];//The two sub-arrays
int sum1=0,sum2=0;//These store the sum of the elements of the 2 subarrays respectively
for(i=0;i<A.length;i++)
{
//Calculate the absolute difference of the sums for each element and then add accordingly and thereafter update the sum
    if(abs(sum1+A[i]-sum2)<=abs(sum2+A[i]-sum1))
           {a1.add(A[i]);
            sum1+=A[i];}
    else
           {a2.add(A[i]);
            sum2+=A[i];}
}

这适用于所有整数，无论是正数还是负数。

Answer 3

首先，对数组进行排序，然后将第一个成员放在组中，将第二个成员放在另一个伤口中，这是行不通的，原因如下：

给定输入[1,2,3,100]。结果将是：[1,3] 和 [2,100]，显然是错误的。正确答案应该是：[1,2,3] 和 [100]

你可以在 google 上找到许多针对此问题的优化算法，但由于我假设你是初学者，我将尝试为你提供一个你可以实现的简单算法：

对数组进行排序
从最高值到最低值迭代
每次迭代，计算每组的总和，然后将元素添加到总和最小的组

在循环结束时，您应该有两个相当平衡的数组。示例：

Array: [1,5,5,6,7,10,20]
i1: `[20] []`
i2: `[20] [10]`
i3: `[20] [10,7]`
i4: `[20] [20,7,6]`
i5: `[20,5] [10,7,6]`
i6: `[20,5] [10,7,6,5]`
i7: `[20,5,1] [10,7,6,5]`

总和为 26 和 28。如您所见，我们可以进一步优化解决方案，如果我们交换 5 和 6 导致 [20,6,1] 和 [20,7,5,5] 总和相等。

对于这一步，您可以：

找到所有元素组(x,y)，其中x在第1组，y在第2组，|x-y| < |sum(group1) - sum(group2)|
循环所有组并尝试将 x 与 y 交换，直到得到最小差异
每次交换后检查总和最高的组中的最小值是否大于组的差异，如果是，则将其转移到另一组

该算法总是 return 最佳解决方案，并且比贪心算法好很多。然而，它在复杂性、速度和内存方面并不是最优的。如果需要它用于非常大的阵列并且资源有限，则最佳算法可能会有所不同，具体取决于 speed/memory 比率和可接受的错误百分比。

Answer 4

对于这道题，假设我们可以将数组分成两个子数组，使得它们的和相等。（即使认为它们不相等，它也会起作用）

所以如果数组中元素的总和是S。你的目标是找到总和S/2的子集。你可以为此写一个递归函数。

  int difference = Integer.MAX_VALUE;

  public void recursiveSum(int[] array, int presentSum, int index,Set<Integer> presentSet){
       if(index == array.length){
          if(Math.abs(presentSum - (S/2)) < difference)){
             difference = Math.abs(presentSum - (S/2);
             // presentSet is your answer
             return;
          }
       }
       recursiveSum(array,presentSum,index+1,presentSet); // don't consider the present element in the final solution
       presentSet.add(array[index]);
       recursiveSum(array,presentSum + array[index],index+1,presentSet); //consider the present element in the final solution

 }

您也可以为此编写等效的 O(N^2) 动态编程代码。我只是在演示这个想法。

因此，当您找到总和为 S/2 的集合时，您已自动将数组分成总和相同的两部分（此处为 S/2）。

Answer 5

我似乎找到了完美的解决方案。 Java 下面的程序完美运行。唯一的假设是，给定的问题有唯一的解决方案（只有一个解决方案）。这个假设意味着- 只有非零数。我把程序放在下面。我要求每个人都告诉我程序是否会在某些情况下失败，或者它是否会以某种方式 improved/optimized。 感谢 Alexandru Severin 先生的 算法作为此主题中的答案之一发布。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindMinimumDifference {

static List<Integer> list1= new ArrayList<>();
static List<Integer> list2= new ArrayList<>();

public static void main(String[] args) {
    int[] arr= new int[]{3,-2,9,7};  
    // tested for these sample data:- [1,5,9,3] ; [4,3,5,9,11] ; 
//[7,5,11,2,13,15,14] ; [3,2,1,7,9,11,13] ; 
    //[3,1,0,5,6,9] ; [6,8,10,2,4,0] ; [3,1,5,7,0] ; [4,-1,5,-3,7] ; [3,-2,9,7]

    System.out.println("the minimum possible difference is: "+returnMinDiff(arr));
    System.out.println("the two resulting set of nos. are: "+list1+" and "+list2);
}

private static int  returnMinDiff(int[] array){
    int diff=-1;
    Arrays.sort(array);

    for(int a:array){
        int sumOfList1=0;
        int sumOfList2=0;

        for(Integer i:list1){
            sumOfList1+=i;
        }
        for(Integer i:list2){
            sumOfList2+=i;
        }
        if(sumOfList1<=sumOfList2){
        list1.add(a);
        }else{
            list2.add(a);
        }
    }

    List<Integer> list3=new ArrayList<>(list1);   
    List<Integer> list4= new ArrayList<>(list2); 
    if(list3.size()!=list4.size()){     // both list should contain equal no. of entries. 
        //If not, add 0 to the list having lesser no. of entries
        if(list3.size()<list4.size()){
            list3.add(0);
        }else{
            list4.add(0);
        }
    }
    Map<Integer, List<Integer>> mapOfProbables= new HashMap<Integer, List<Integer>>();
    int probableValueCount=0;
    for(int i=0; i<list3.size();i++){  
        for(int j=0; j<list4.size();j++){
            if(abs(list3.get(i)-list4.get(j))
   <abs(getSumOfEntries(list3)-getSumOfEntries(list4))){
                List<Integer> list= new ArrayList<>();
                list.add(list3.get(i));
                list.add(list4.get(j));    
                mapOfProbables.put(probableValueCount++, list);
            }
        }
    }
    int minimumDiff=abs(getSumOfEntries(list1)-getSumOfEntries(list2));
    List resultList= new ArrayList<>();
    for(List probableList:mapOfProbables.values()){ 
        list3=new ArrayList<>(list1);   
        list4= new ArrayList<>(list2);
        list3.remove(probableList.get(0));
        list4.remove(probableList.get(1));
        list3.add((Integer)probableList.get(1));
        list4.add((Integer)probableList.get(0));
        if(minimumDiff>abs(getSumOfEntries(list3)-getSumOfEntries(list4))){ // valid exchange 
                minimumDiff=abs(getSumOfEntries(list3)-getSumOfEntries(list4));
                resultList=probableList;
        }

    }

    if(resultList.size()>0){   // forming the two set of nos. whose difference of sum comes out to be minimum
        list1.remove(resultList.get(0));
        list2.remove(resultList.get(1));
        if(!resultList.get(1).equals(0) )   // (resultList.get(1).equals(0) && !list1.contains(0))
            list1.add((Integer)resultList.get(1));
        if(!resultList.get(0).equals(0) || (resultList.get(0).equals(0) && list2.contains(0)))
            list2.add((Integer)resultList.get(0));
    }

    return minimumDiff; // returning the minimum possible difference
}

private static int getSumOfEntries(List<Integer> list){
    int sum=0;
    for(Integer i:list){
        sum+=i;
    }
    return sum;
}
private static int abs(int i){
    if(i<=0) 
        i=-i;
    return i;
}
}

如何将一组数字分成两组，使它们之和的差最小

How to divide a set of numbers into two sets such that the difference of their sum is minimum

java

arrays

partition