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

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

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

PS-我在这里看了一下，但找不到任何具体的解决方案。 这里似乎给出了最可能的解决方案 – 将一个arrays分成两组，差别很小 。 但我无法从该线程中收集如何编写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 list1= new ArrayList(); List 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 list3=new ArrayList(list1); List list4= new ArrayList(list2); Map<Integer, List> mapOfProbables= new HashMap<Integer, List>(); 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 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 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

首先，对数组进行排序然后将第一个成员放入组中，然后将第二个成员放入另一个创建中，这样就不会起作用了

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

你可以在google上找到很多关于这个问题的优化算法，但是因为我认为你是初学者，我会尝试给你一个简单的算法，你可以实现：

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结果[20,6,1]和[20,7,5,5]的总和是相等的。

对于此步骤，您可以：

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

该算法将始终返回最佳解决方案，并且比贪婪方法好得多。 然而，就复杂性，速度和记忆而言，它并不是最佳的。 如果对于非常大的arrays需要它并且资源有限，则最佳算法可能根据速度/存储比率和接受的误差百分比而不同。

Answer 2

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

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

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

当集合中的数字与其基数大小相同或更小时，这种启发式在实践中运行良好，但不能保证产生最佳可能的分区。

首先，您需要将输入放在可排序的集合中，例如List。

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

2）创建2个结果集。

3）迭代排序的输入。 如果索引甚至将项放在result1中，则将该项放在result2中。

  List input = new ArrayList(); Collections.sort(input); Set result1 = new HashSet(); Set result2 = new HashSet(); 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

我似乎已经有了完美的解决方案。 Java程序下面的工作完美。 唯一的假设是，给定的问题有唯一的解决方案（只有一个解决方案）。 这个假设意味着 – 只有非零数字 。 我把这个程序放在下面。 我请求每个人告诉程序是否可能在某些情况下失败，或者是否可以某种方式改进/优化。 对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 list1= new ArrayList<>(); static List 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 list3=new ArrayList<>(list1); List 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()> mapOfProbables= new HashMap>(); int probableValueCount=0; for(int i=0; i 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 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 4

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

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

  int difference = Integer.MAX_VALUE; public void recursiveSum(int[] array, int presentSum, int index,Set 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

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

 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 

这适用于所有整数，无论​​是积极的还是消极的。