将一个数组分成两组，最小差异
我遇到的一个面试问题：
给定一组数字，将数字分成两组，使得两组数字之和的差值最小。
这是我的想法，但我不确定这是否是一个正确的解决scheme：
- sorting数组
- 以前两个元素为例，把它们看作是2个元素（每个元素都有1个元素）
- 从数组中取下一个元素。
- 现在决定这个元素去哪个集合（通过计算总和应该是最小的）
- 重复
这是正确的解决scheme吗？ 我们可以做得更好吗？
你所描述的问题是分区问题 。 find一个最佳的解决scheme是NP完整的，但是有一些近似在大多数情况下几乎是完美的。
事实上，你所描述的algorithm是操场上孩子们挑选球队的方式。 如果该集合中的数字具有相似的数量级，则该贪婪algorithm执行得非常好。 当然，这不是最好的解决scheme，但考虑到这个问题是如何完成的，它的简单性让它变得非常好。
“美国科学家”这篇文章对这个问题作了很好的分析，你应该仔细阅读： “最简单的难题” 。
不，这不行。 没有多项式时间解（除非P = NP）。 你可以做的最好的只是看看所有不同的子集…
http://en.wikipedia.org/wiki/Subset_sum_problem
考虑一下列表[0,1,5,6]。
当最佳答案实际上是{0,1,5}和{6}时，您将声明{0,5}和{1,6}
组合方式的组合：
import itertools as it def min_diff_sets(data): """ Parameters: - `data`: input list. Return: - min diff between sum of numbers in two sets """ if len(data) == 1: return data[0] s = sum(data) # `a` is list of all possible combinations of all possible lengths (from 1 # to len(data) ) a = [] for i in range(1, len(data)): a.extend(list(it.combinations(data, i))) # `b` is list of all possible pairs (combinations) of all elements from `a` b = it.combinations(a, 2) # `c` is going to be final correct list of combinations. # Let's apply 2 filters: # 1. leave only pairs where: sum of all elements == sum(data) # 2. leave only pairs where: flat list from pairs == data c = filter(lambda x: sum(x[0])+sum(x[1])==s, b) c = filter(lambda x: sorted([i for sub in x for i in sub])==sorted(data), c) # `res` = [min_diff_between_sum_of_numbers_in_two_sets, # ((set_1), (set_2)) # ] res = sorted([(abs(sum(i[0]) - sum(i[1])), i) for i in c], key=lambda x: x[0]) return min([i[0] for i in res]) if __name__ == '__main__': assert min_diff_sets([10, 10]) == 0, "1st example" assert min_diff_sets([10]) == 10, "2nd example" assert min_diff_sets([5, 8, 13, 27, 14]) == 3, "3rd example" assert min_diff_sets([5, 5, 6, 5]) == 1, "4th example" assert min_diff_sets([12, 30, 30, 32, 42, 49]) == 9, "5th example" assert min_diff_sets([1, 1, 1, 3]) == 0, "6th example" 一个小的变化：颠倒顺序 – 从最大的数字开始，并减less。 这将最大限度地减less错误。
你是否将你的子集sorting为升序或降序？
想想像这样，数组{1,3,5,8,9,25}
如果你要分裂，你会有{1,8,9} = 18 {3,5,25} = 33
如果按照降序sorting，结果会好很多
{25,1} = 26 {9,8,5,3} = 25
所以你的解决scheme基本上是正确的，它只需要确保首先采取最大的价值。
编辑：读tskuzzy的职位。 我的工作不正常
这是背包和子集和问题的变体。 在子集和问题中，给定n个正整数和一个值k，我们必须find其值小于或等于k的子集的和。 在上面的问题中，我们给出了一个数组，在这里我们必须find总和小于或等于total_sum（数组值总和）的子集。 所以子集和可以通过使用背包algorithm中的variables来获得，通过将利润作为给定的数组值来获得。 最后的答案是total_sum-dp [n] [total_sum / 2]。 看看下面的代码清楚的理解。
#include<iostream> #include<cstdio> using namespace std; int main() { int n; cin>>n; int arr[n],sum=0; for(int i=1;i<=n;i++) cin>>arr[i],sum+=arr[i]; int temp=sum/2; int dp[n+1][temp+2]; for(int i=0;i<=n;i++) { for(int j=0;j<=temp;j++) { if(i==0 || j==0) dp[i][j]=0; else if(arr[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-arr[i]]+arr[i]); else { dp[i][j]=dp[i-1][j]; } } } cout<<sum-2*dp[n][temp]<<endl; }
这可以使用BST来解决。
首先sorting数组，说arr1
要开始用arr1的最后一个元素创build另一个arr2（从arr1中删除这个ele）
现在：重复这些步骤直到没有交换发生。
- 检查arr1是否可以使用BST移动到arr2的元素，以便比较直到现在发现的最小MIN差异。
- 如果我们发现一个元素将这个元素移动到arr2并再次转到step1。
- 如果在上面的步骤中没有find任何元素，请对arr2＆arr1执行步骤1和2。 即现在检查arr2中是否有任何可以移动到arr1的元素
- 继续步骤1-4，直到我们不需要任何交换。
- 我们得到解决scheme。
示例Java代码：
import java.util.ArrayList; import java.util.Collections; import java.util.List; /** * Divide an array so that the difference between these 2 is min * * @author shaikhjamir * */ public class DivideArrayForMinDiff { /** * Create 2 arrays and try to find the element from 2nd one so that diff is * min than the current one */ private static int sum(List<Integer> arr) { int total = 0; for (int i = 0; i < arr.size(); i++) { total += arr.get(i); } return total; } private static int diff(ArrayList<Integer> arr, ArrayList<Integer> arr2) { int diff = sum(arr) - sum(arr2); if (diff < 0) diff = diff * -1; return diff; } private static int MIN = Integer.MAX_VALUE; private static int binarySearch(int low, int high, ArrayList<Integer> arr1, int arr2sum) { if (low > high || low < 0) return -1; int mid = (low + high) / 2; int midVal = arr1.get(mid); int sum1 = sum(arr1); int resultOfMoveOrg = (sum1 - midVal) - (arr2sum + midVal); int resultOfMove = (sum1 - midVal) - (arr2sum + midVal); if (resultOfMove < 0) resultOfMove = resultOfMove * -1; if (resultOfMove < MIN) { // lets do the swap return mid; } // this is positive number greater than min // which mean we should move left if (resultOfMoveOrg < 0) { // 1,10, 19 ==> 30 // 100 // 20, 110 = -90 // 29, 111 = -83 return binarySearch(low, mid - 1, arr1, arr2sum); } else { // resultOfMoveOrg > 0 // 1,5,10, 15, 19, 20 => 70 // 21 // For 10 // 60, 31 it will be 29 // now if we move 1 // 71, 22 ==> 49 // but now if we move 20 // 50, 41 ==> 9 return binarySearch(mid + 1, high, arr1, arr2sum); } } private static int findMin(ArrayList<Integer> arr1) { ArrayList<Integer> list2 = new ArrayList<>(arr1.subList(arr1.size() - 1, arr1.size())); arr1.remove(arr1.size() - 1); while (true) { int index = binarySearch(0, arr1.size(), arr1, sum(list2)); if (index != -1) { int val = arr1.get(index); arr1.remove(index); list2.add(val); Collections.sort(list2); MIN = diff(arr1, list2); } else { // now try for arr2 int index2 = binarySearch(0, list2.size(), list2, sum(arr1)); if (index2 != -1) { int val = list2.get(index2); list2.remove(index2); arr1.add(val); Collections.sort(arr1); MIN = diff(arr1, list2); } else { // no switch in both the cases break; } } } System.out.println("MIN==>" + MIN); System.out.println("arr1==>" + arr1 + ":" + sum(arr1)); System.out.println("list2==>" + list2 + ":" + sum(list2)); return 0; } public static void main(String args[]) { ArrayList<Integer> org = new ArrayList<>(); org = new ArrayList<>(); org.add(1); org.add(2); org.add(3); org.add(7); org.add(8); org.add(10); findMin(org); } }
开始添加数字，但每次与下一个数字进行比较，如果总和大于或等于，则将该数字移至其他数组。
现在，下一个数字直接转移到其他数组，除非新的总和<第一个总和，然后你可以重复剩余的数字相同的过程。 通过这种方式，我们最终只能在一次迭代中解决您的问题。
如果数组包含上面的负数将无法正常工作。
经过很多的思考和组合，我想出了以下的解决scheme。
1. Sort and add elements at the same time.(To reduce one more iteration on array.) 2. Do (Sum/2) and find out median of sorted array (array/2)(median can be used to optimize more) 3. Pick up highest and lowest one by one until its near or equal to (sum/2)
这个解决scheme也适用于负值。
int ModDiff(int a, int b) { if(a < b)return b - a; return ab; } int EqDiv(int *a, int l, int *SumI, int *SumE) { static int tc = 0; int min = ModDiff(*SumI,*SumE); for(int i = 0; i < l; i++) { swap(a,0,i); a++; int m1 = EqDiv(a, l-1, SumI,SumE); a--; swap(a,0,i); *SumI = *SumI + a[i]; *SumE = *SumE - a[i]; swap(a,0,i); a++; int m2 = EqDiv(a,l-1, SumI,SumE); a--; swap(a,0,i); *SumI = *SumI - a[i]; *SumE = *SumE + a[i]; min = min3(min,m1,m2); } return min;
}
调用SumI = 0和SumE = sumof中的所有元素的函数。 这个O（n！）解决scheme确实计算了我们可以将给定数组分成两部分的方式，这样的差别是最小的。 但绝对不实际，由于n！ 时间复杂性期待使用DP来改善这一点。
尝试这个 ：
partition(i, A, B) = min(partition(i+1, AUA[i], B), partition(i+1, A, BUA[i])) where i< n Absolute(Sigma(A) - Sigma(B)) where i = nn : number of elements in Original Array
请检查我为这个问题写的这个逻辑。 它适用于我检查的几个场景。 请评论解决方法，方法：
- 对主arrays进行sorting并将其分成2组。
- 然后根据代码中提到的条件，通过移动和交换元素从一个数组到另外一个开始使团队平等。
如果和的差值小于大数组（总和较大的数组）的最小数，那么将元素从较大的数组移到较小的数组。 换位发生在条件上，即来自更大arrays中的值小于或等于差值的元素。当来自更大arrays的所有元素大于差值时，移位停止和交换发生。 我只是交换数组的最后一个元素（它可以通过find哪两个元素交换更有效），但仍然工作。 让我知道这种逻辑是否在任何情况下失败。
public class SmallestDifference { static int sum1 = 0, sum2 = 0, diff, minDiff; private static List<Integer> minArr1; private static List<Integer> minArr2; private static List<Integer> biggerArr; /** * @param args */ public static void main(String[] args) { SmallestDifference sm = new SmallestDifference(); Integer[] array1 = { 2, 7, 1, 4, 5, 9, 10, 11 }; List<Integer> array = new ArrayList<Integer>(); for (Integer val : array1) { array.add(val); } Collections.sort(array); CopyOnWriteArrayList<Integer> arr1 = new CopyOnWriteArrayList<>(array.subList(0, array.size() / 2)); CopyOnWriteArrayList<Integer> arr2 = new CopyOnWriteArrayList<>(array.subList(array.size() / 2, array.size())); diff = Math.abs(sm.getSum(arr1) - sm.getSum(arr2)); minDiff = array.get(0); sm.updateSum(arr1, arr2); System.out.println(arr1 + " : " + arr2); System.out.println(sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff); int k = arr2.size(); biggerArr = arr2; while (diff != 0 && k >= 0) { while (diff != 0 && sm.findMin(biggerArr) < diff) { sm.swich(arr1, arr2); int sum1 = sm.getSum(arr1), sum2 = sm.getSum(arr2); diff = Math.abs(sum1 - sum2); if (sum1 > sum2) { biggerArr = arr1; } else { biggerArr = arr2; } if (minDiff > diff || sm.findMin(biggerArr) > diff) { minDiff = diff; minArr1 = new CopyOnWriteArrayList<>(arr1); minArr2 = new CopyOnWriteArrayList<>(arr2); } sm.updateSum(arr1, arr2); System.out.println("Shifting : " + sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff); } while (k >= 0 && minDiff > array.get(0) && minDiff != 0) { sm.swap(arr1, arr2); diff = Math.abs(sm.getSum(arr1) - sm.getSum(arr2)); if (minDiff > diff) { minDiff = diff; minArr1 = new CopyOnWriteArrayList<>(arr1); minArr2 = new CopyOnWriteArrayList<>(arr2); } sm.updateSum(arr1, arr2); System.out.println("Swapping : " + sum1 + " - " + sum2 + " = " + diff + " : minDiff = " + minDiff); k--; } k--; } System.out.println(minArr1 + " : " + minArr2 + " = " + minDiff); } private void updateSum(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) { SmallestDifference sm1 = new SmallestDifference(); sum1 = sm1.getSum(arr1); sum2 = sm1.getSum(arr2); } private int findMin(List<Integer> biggerArr2) { Integer min = biggerArr2.get(0); for (Integer integer : biggerArr2) { if(min > integer) { min = integer; } } return min; } private int getSum(CopyOnWriteArrayList<Integer> arr) { int sum = 0; for (Integer val : arr) { sum += val; } return sum; } private void swap(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) { int l1 = arr1.size(), l2 = arr2.size(), temp2 = arr2.get(l2 - 1), temp1 = arr1.get(l1 - 1); arr1.remove(l1 - 1); arr1.add(temp2); arr2.remove(l2 - 1); arr2.add(temp1); System.out.println(arr1 + " : " + arr2); } private void swich(CopyOnWriteArrayList<Integer> arr1, CopyOnWriteArrayList<Integer> arr2) { Integer e; if (sum1 > sum2) { e = this.findElementJustLessThanMinDiff(arr1); arr1.remove(e); arr2.add(e); } else { e = this.findElementJustLessThanMinDiff(arr2); arr2.remove(e); arr1.add(e); } System.out.println(arr1 + " : " + arr2); } private Integer findElementJustLessThanMinDiff(CopyOnWriteArrayList<Integer> arr1) { Integer e = arr1.get(0); int tempDiff = diff - e; for (Integer integer : arr1) { if (diff > integer && (diff - integer) < tempDiff) { e = integer; tempDiff = diff - e; } } return e; }
}
一个可能的解决scheme在这里 – https://stackoverflow.com/a/31228461/4955513这个Java程序似乎解决了这个问题，只要满足一个条件; – 只有一个解决scheme的问题。
#include<bits/stdc++.h> using namespace std; bool ison(int i,int x) { if((i>>x) & 1)return true; return false; } int main() { // cout<<"enter the number of elements : "; int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; int sumarr1[(1<<n)-1]; int sumarr2[(1<<n)-1]; memset(sumarr1,0,sizeof(sumarr1)); memset(sumarr2,0,sizeof(sumarr2)); int index=0; vector<int>v1[(1<<n)-1]; vector<int>v2[(1<<n)-1]; for(int i=1;i<(1<<n);i++) { for(int j=0;j<n;j++) { if(ison(i,j)) { sumarr1[index]+=a[j]; v1[index].push_back(a[j]); } else { sumarr2[index]+=a[j]; v2[index].push_back(a[j]); } }index++; } int ans=INT_MAX; int ii; for(int i=0;i<index;i++) { if(abs(sumarr1[i]-sumarr2[i])<ans) { ii=i; ans=abs(sumarr1[i]-sumarr2[i]); } } cout<<"first partitioned array : "; for(int i=0;i<v1[ii].size();i++) { cout<<v1[ii][i]<<" "; } cout<<endl; cout<<"2nd partitioned array : "; for(int i=0;i<v2[ii].size();i++) { cout<<v2[ii][i]<<" "; } cout<<endl; cout<<"minimum difference is : "<<ans<<endl; }
许多答案都提到在一个非常可接受的时间内获得“近似”的解决scheme。 但是由于在采访中被问到，我不指望他们需要一个近似algorithm。 另外我不指望他们也需要一个天真的指数algorithm。
为了解决这个问题，假设已知数字的最大值，可以使用dynamic规划在多项式时间内解决问题。 请参阅此链接~bcdean/dp_practice/dp_4.swf
HI I think This Problem can be solved in Linear Time on a sorted array , no Polynomial Time is required , rather than Choosing Next Element u can choose nest two Element and decide which side which element to go. in This Way in this way minimize the difference, let suppose {0,1,5,6} , choose {0,1} {0} , {1} choose 5,6 {0,6}, {1,5} but still that is not exact solution , now at the end there will be difference of sum in 2 array let suppose x but there can be better solution of difference of (less than x) for that Find again 1 greedy approach over sorted half sized array and move x/2(or nearby) element from 1 set to another or exchange element of(difference x/2) so that difference can be minimized***
