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

Question

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

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

附:我已经看了这里，但找不到任何具体的解决方案。这里似乎给出了最可能的解决方案——将一个数组分成差别最小的两组。但是我无法从这个思路中总结出如何编写一个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

对此我似乎有了完美的解决方案。下面的Java程序运行良好。唯一的假设是，给定的问题有唯一的解(只有一个解)。这个假设意味着-只有非零数字。我把程序放在下面。我请求每个人告诉我这个程序在某些情况下是否会失败，或者它是否可以在某些方面得到改进/优化。亚历山德鲁·塞弗林先生的算法是这个帖子的答案之一。

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

Answer 2

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

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

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

当集合中的数字与其基数大小大致相同或更小时，这种启发式方法在实践中效果很好，但不能保证产生最佳分区。

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

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

2)创建2个结果集。

3）遍历排序的输入。如果索引甚至将项目放在结果1中，则将项目放在结果2中。

  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 3

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

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

你可以在谷歌上找到很多针对这个问题的优化算法，但由于我假设你是一个初学者，我会尝试给你一个简单的算法，你可以实现：

1. 对数组进行排序
2. 从最高值迭代到最低值
3. 对于每次迭代，计算每个组的总和，然后将元素以最小总和添加到组中

在循环的末尾，您应该有两个相当平衡的数组。例子：

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，结果 ，则总和相等。

对于此步骤，您可以：

1. 查找所有元素组（x， y）其中x在Group1中，y在Group2中，并且|x-y|

该算法将始终返回最佳解决方案，并且比贪婪的方法要好得多。但是，它在复杂性，速度和内存方面并不是最佳的。如果非常大的阵列需要它并且资源有限，则最佳算法可能会因速度/内存比率和可接受的错误百分比而异。