划分的数组大小相等的两个子集具有值的总和最小差 [英] Dividing an array into two subsets of equal sizes having minimum difference in sum of values
问题描述
给定一组n个整数的，除以该组中的n / 2尺寸的两个子集的每个，使得两个子集的总和的差作为最小的越好。如果n是偶数，则两个子集的大小必须严格N / 2，并且如果n是奇数，则一个子集的大小必须是（N-1）的其他子集/ 2和大小必须是第（n + 1）/ 2
Given a set of n integers, divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subsets must be strictly n/2 and if n is odd, then size of one subset must be (n-1)/2 and size of other subset must be (n+1)/2.
例如，让组给定为{3，4，5，-3，100，1，89，54，23，20}，集合的大小为10。此设置的输出应为{4,100 1，23，20}和{3,5，-3，89，54}。两个输出子集在两个子集元素的大小5总和是一样的（148和148）。
另一个例子，其中n为奇数。让组给定为{23，45，-34，12，0，98，-99，4，189 1，-1，4}。输出子集应{45，-34，12，98，-1}和{23，0，-99，4，189，4}。元件在两个子集的总和分别为120和121。
For example, let given set be {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, the size of set is 10. Output for this set should be {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. Both output subsets are of size 5 and sum of elements in both subsets is same (148 and 148). Another example where n is odd. Let given set be {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}. The output subsets should be {45, -34, 12, 98, -1} and {23, 0, -99, 4, 189, 4}. The sums of elements in two subsets are 120 and 121 respectively.
一番搜索之后，我发现这个问题是一个NP难。因此，一个多项式时间解是不可能的。
不过，我在想东西在这行：
After much searching, I found out this problem is NP-Hard. Therefore, a polynomial time solution is not possible. However, I was thinking something in lines of this:
- 先初始化子集作为第一要素。
- 初始化第二子集的第二个元素。
- 然后根据哪个子集是尺寸较小和的总和是缺乏，其中子集，我将插入下一个元件。
以上可以实现线性时间，我猜。
The above might achieve a linear time, I guess.
然而，这里给出的解决方案是太复杂： HTTP：//www.geeksforgeeks。组织/拔河-/ 。我无法理解。因此，我只想问一句，是我的解决方案是否正确？考虑到这一事实，这是一个NP-Hard问题，我想这应该怎么办？如果没有，可有人请解释真的一样简单，究竟链接附作品code？谢谢！
However, the solution given here is way too complicated: http://www.geeksforgeeks.org/tug-of-war/. I couldn't understand it. Therefore, I just want to ask, is my solution correct? Considering the fact that this is a NP-Hard problem, I think it should do? And if not, can someone please explain in like really brief, how exactly the code on the link attached works? Thanks!
推荐答案
您的解决方案是错误的。
Your solution is wrong.
这是要解决的子集和问题/划分问题贪婪的方法，即失败。
It's a greedy approach to solve the Subset-Sum problem/ Partition Problem, that fails.
下面是一个简单的反例：
Here is a simple counter example:
arr = [1,2,3]
您的解决方案将赋予A = {1}，B = {2}，然后选择分配3〜 A ，并获得 A = {1,3}，b = {2} - 这是不是最佳的，因为最佳的解决方案是 A = {1,2}，b = {3}
Your solution will assign A={1}, B={2}, and then chose to assign 3 to A, and get A={1,3}, B={2} - which is not optimal, since the optimal solution is A={1,2}, b={3}
做的是用动态规划，遵循递推公式的正确方法：
The correct way to do it is using Dynamic Programming, by following the recursive formulas:
D(x,i) = false i < 0
D(0,i) = true
D(x,i) = D(x,i-1) OR D(x-arr[i],i-1)
它可以有效地利用动态规划通过构建下面的复发自下而上的表来完成。
It can be done efficiently using Dynamic Programming by building a table that follows the recurrence bottom-up.
该表将是大小（SUM / 2 + 1）*（N + 1）（其中 SUM 是所有元素的总和），然后找到该表中的最大值，这样 D（X，N）=真
The table will be of size (SUM/2 + 1)*(n+1) (where SUM is the sum of all elements), and then find the maximal value in the table such that D(x,n) = true
这篇关于划分的数组大小相等的两个子集具有值的总和最小差的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
