如何划分的一组数字的分成两组，使得它们的和的差为最小 [英] How to divide a set of numbers into two sets such that the difference of their sum is minimum
问题描述
如何写一个Java程序为一组数字的分成两组，使得它们各自的数字的总和的差，是最小的。
例如，我有一个包含integers-数组[5,4,8,2]。我可以把它分成两arrays- [8,2]和[5,4]。假设给定的数字，可以在上面的例子像一个独特的解决方案，如何编写Java程序来实现的解决方案。这将是即使我能找出尽可能小的差异罚款。
比方说，我的方法接收数组作为参数。该方法具有对第一划分接收成两个阵列的阵列，然后添加其中包含的整数。此后，它具有以返回它们之间的差，使得该差为最小的可能
P.S.-我有这里看看左右，但找不到任何具体的解决办法了这一点。最有可能的解决方案似乎是给这里 - <一个href=\"http://stackoverflow.com/questions/6597180/divide-an-array-into-two-sets-with-minimal-difference\">divide数组分成两组与最小差异。但我无法从那个线程收集我怎么能写一个Java程序来获得一个明确的解决问题的办法。
编辑：
看着@Alexandru塞韦林的评论之后，我尝试了Java程序。它适用于一组号码[1,3,5,9]，但对于另一组[4,3,5,9，11]不起作用。下面是程序。请建议的变化： -
进口的java.util.ArrayList;
进口java.util.Arrays中;
进口的java.util.HashMap;
进口的java.util.List;
进口的java.util.Map;公共类FindMinimumDifference {
公共静态无效的主要（字串[] args）{
INT [] =改编新INT [] {4,3,5,9，11};
FindMinimumDifference的obj =新FindMinimumDifference（）;
obj.returnMinDiff（ARR）;
}私人诠释returnMinDiff（INT []数组）{
INT的diff = -1;
Arrays.sort（数组）;
清单＆LT;整数GT; list1的=新的ArrayList＆LT;＆GT;（）;
清单＆LT;整数GT;列表2 =新的ArrayList＆LT;＆GT;（）;
INT sumOfList1 = 0;
INT sumOfList2 = 0;
对于（INT一：数组）{
对于（整数i：list1的）{
sumOfList1 + =我;
}
对于（整数i：列表2）{
sumOfList2 + =我;
}
如果（sumOfList1＆LT; = sumOfList2）{
list1.add（一）;
}其他{
list2.add（一）;
}
} 清单＆LT;整数GT;项目list3 =新的ArrayList＆LT;＆GT;（list1的）;
清单＆LT;整数GT; list4 =新的ArrayList＆LT;＆GT;（列表2）;
地图＆LT;整数，列表与LT;整数GT;＆GT; mapOfProbables =新的HashMap＆LT;整数，列表与LT;整数GT;＆GT;（）;
INT probableValueCount = 0;
的for（int i = 0; I＆LT; list1.size（）;我++）{
对于（INT J = 0; J＆LT; list2.size（）; J ++）{
如果（ABS（list1.get（ⅰ）-list2.get（J））≤;
ABS（getSumOfEntries（list1的）-getSumOfEntries（列表2）））{
清单＆LT;整数GT;名单=新的ArrayList＆LT;＆GT;（）;
list.add（list1.get（I））;
list.add（list2.get（J））;
mapOfProbables.put（probableValueCount ++，清单）;
}
}
}
INT minimumDiff = ABS（getSumOfEntries（list1的）-getSumOfEntries（列表2））;
清单resultList =新的ArrayList＆LT;＆GT;（）;
为（列表probableList：mapOfProbables.values（））{
list3.remove（probableList.get（0））;
list4.remove（probableList.get（1））;
list3.add（（整数）probableList.get（1））;
list4.add（（整数）probableList.get（0））;
如果（minimumDiff＆GT; ABS（getSumOfEntries（项目list3）-getSumOfEntries（list4）））{
//有效汇率
minimumDiff = ABS（getSumOfEntries（项目list3）-getSumOfEntries（list4））;
resultList = probableList;
} } 的System.out.println（minimumDiff）; 如果（resultList.size（）大于0）{
list1.remove（resultList.get（0））;
list2.remove（resultList.get（1））;
list1.add（（整数）resultList.get（1））;
list2.add（（整数）resultList.get（0））;
} 的System.out.println（list1的++列表2）; //两个所得设定的
//使用修改后的数据给预期结果号码 返回minimumDiff;
}私有静态诠释getSumOfEntries（列表＆LT;整数GT;名单）{
INT总和= 0;
对于（整数i：名单）{
总和+ =我;
}
返回总和;
}
私有静态诠释ABS（int i）以{
如果（ⅰ＆下; = 0）
I = -i;
返回我;
}
}
我似乎已经为这个完美的解决方案。下面的Java程序完美的作品。唯一的假设是，在给定的问题具有独特的溶液（只有一个溶液）。这种假设implies-的仅非零数字。我把下面的程序。我请求大家说，如果该计划可能会失败某些情况下，或以某种方式是否可以改进/优化。 积分先生亚历塞韦林的算法张贴在这个线程的答案之一。
进口的java.util.ArrayList;
进口java.util.Arrays中;
进口的java.util.HashMap;
进口的java.util.List;
进口的java.util.Map;公共类FindMinimumDifference {静态列表＆LT;整数GT; list1的=新的ArrayList＆LT;＆GT;（）;
静态列表＆LT;整数GT;列表2 =新的ArrayList＆LT;＆GT;（）;公共静态无效的主要（字串[] args）{
INT [] =改编新INT [] {3，-2,9,7};
//测试了这些样本数据： - [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（最小可能差为：+ returnMinDiff（改编））;
的System.out.println（所得号的组中的两个是：+ list1的+和+列表2）;
}私有静态诠释returnMinDiff（INT []数组）{
INT的diff = -1;
Arrays.sort（数组）; 对于（INT一：数组）{
INT sumOfList1 = 0;
INT sumOfList2 = 0; 对于（整数i：list1的）{
sumOfList1 + =我;
}
对于（整数i：列表2）{
sumOfList2 + =我;
}
如果（sumOfList1＆LT; = sumOfList2）{
list1.add（一）;
}其他{
list2.add（一）;
}
} 清单＆LT;整数GT;项目list3 =新的ArrayList＆LT;＆GT;（list1的）;
清单＆LT;整数GT; list4 =新的ArrayList＆LT;＆GT;（列表2）;
如果（list3.size（）！= list4.size（））{//这两个列表应包含等于没有。的条目。
//如果不加0具有不小的列表。项
如果（list3.size（）＆所述; list4.size（））{
list3.add（0）;
}其他{
list4.add（0）;
}
}
地图＆LT;整数，列表与LT;整数GT;＆GT; mapOfProbables =新的HashMap＆LT;整数，列表与LT;整数GT;＆GT;（）;
INT probableValueCount = 0;
的for（int i = 0; I＆LT; list3.size（）;我++）{
对于（INT J = 0; J＆LT; list4.size（）; J ++）{
如果（ABS（list3.get（I）-list4.get（J））
＆LT; ABS（getSumOfEntries（项目list3）-getSumOfEntries（list4）））{
清单＆LT;整数GT;名单=新的ArrayList＆LT;＆GT;（）;
list.add（list3.get（I））;
list.add（list4.get（J））;
mapOfProbables.put（probableValueCount ++，清单）;
}
}
}
INT minimumDiff = ABS（getSumOfEntries（list1的）-getSumOfEntries（列表2））;
清单resultList =新的ArrayList＆LT;＆GT;（）;
为（列表probableList：mapOfProbables.values（））{
项目list3 =新的ArrayList＆LT;＆GT;（list1的）;
list4 =新的ArrayList＆LT;＆GT;（列表2）;
list3.remove（probableList.get（0））;
list4.remove（probableList.get（1））;
list3.add（（整数）probableList.get（1））;
list4.add（（整数）probableList.get（0））;
如果（minimumDiff＆GT; ABS（getSumOfEntries（项目list3）-getSumOfEntries（list4）））{//有效汇率
minimumDiff = ABS（getSumOfEntries（项目list3）-getSumOfEntries（list4））;
resultList = probableList;
} } 如果（resultList.size（）大于0）{//形成两个组号的。总和的差异出来是最低
list1.remove（resultList.get（0））;
list2.remove（resultList.get（1））;
如果//（resultList.get（1）.equals（0）！）（resultList.get（1）.equals（0）及＆放大器;！list1.contains（0））
list1.add（（整数）resultList.get（1））;
如果（resultList.get（0）.equals（0）||（resultList.get（0）.equals（0）及！＆放大器; list2.contains（0）））
list2.add（（整数）resultList.get（0））;
} 返回minimumDiff; //返回的最小可能差
}私有静态诠释getSumOfEntries（列表＆LT;整数GT;名单）{
INT总和= 0;
对于（整数i：名单）{
总和+ =我;
}
返回总和;
}
私有静态诠释ABS（int i）以{
如果（ⅰ＆下; = 0）
I = -i;
返回我;
}
}
How to write a Java Program to divide a set of numbers into two sets such that the difference of the sum of their individual numbers, is minimum.
For example, I have an array containing integers- [5,4,8,2]. I can divide it into two arrays- [8,2] and [5,4]. Assuming that the given set of numbers, can have a unique solution like in above example, how to write a Java program to achieve the solution. It would be fine even if I am able to find out that minimum possible difference. Let's say my method receives an array as parameter. That method has to first divide the array received into two arrays, and then add the integers contained in them. Thereafter, it has to return the difference between them, such that the difference is minimum possible.
P.S.- I have had a look around here, but couldn't find any specific solution to this. Most probable solution seemed to be given here- divide an array into two sets with minimal difference . But I couldn't gather from that thread how can I write a Java program to get a definite solution to the problem.
EDIT:
After looking at the comment of @Alexandru Severin, I tried a java program. It works for one set of numbers [1,3,5,9], but doesn't work for another set [4,3,5,9, 11]. Below is the program. Please suggest changes:-
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;
}
}
I seem to have got the perfect solution for this. Below Java program works perfectly. Only assumption is that, the given problem has unique solution (just one solution). This assumption implies- only non-zero number. I am putting the program below. I request everyone to tell if the program could fail for certain scenario, or if it could be improved/optimized in some way. Credits to Mr Alexandru Severin's algorithm posted as one of the answers in this thread.
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;
}
}
这篇关于如何划分的一组数字的分成两组，使得它们的和的差为最小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
