将一个数组分成两个大小相等的子集，使得它们的值之和的差最小。

Question

给定一个包含n个整数的集合，将该集合划分为两个大小均为n/2的子集，以使两个子集的和之差尽可能小。如果n是偶数，则两个子集的大小必须严格为n/2；如果n是奇数，则一个子集的大小必须为(n-1)/2，另一个子集的大小必须为(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, 4}。输出子集应该是{45, -34, 12, 98, -1}和{23, 0, -99, 4, 189, 4}。两个子集中元素的总和分别为120和121。

经过多次搜索，我发现这个问题是NP-Hard问题。因此，不可能有一个多项式时间复杂度的解法。不过，我考虑到以下方法：

1. 将第一个元素初始化为第一个子集。 2. 将第二个元素初始化为第二个子集。 3. 根据哪个子集大小更小，哪个子集中的总和缺乏，我会插入下一个元素。

我猜这样可以实现线性时间复杂度。

然而，这里提供的解决办法太过复杂：http://www.geeksforgeeks.org/tug-of-war/。我无法理解它。因此，我想问一下，我的方法是否正确？考虑到这是一个NP-Hard问题，我认为应该可以吧？如果不行，能否有人简要地解释一下链接上的代码如何工作呢？谢谢！

- John Lui

Answer 1

你的解决方案是错误的。

使用贪心算法解决子集和问题/分割问题是错误的。

这里有一个简单的反例：

arr = [1,2,3]

您的解决方案将分配A={1}，B={2}，然后选择将3分配给A，得到A={1,3}，B={2} - 这不是最优解，因为最优解是A={1,2}，b={3}。

正确的方法是使用动态规划，按照递归公式进行操作：

D(x,i) = false    i < 0
D(0,i) = true
D(x,i) = D(x,i-1) OR D(x-arr[i],i-1)

使用动态规划可以高效地完成，通过自底向上构建遵循递推的表格。

表的大小为(SUM/2 + 1)*(n+1)（其中SUM是所有元素的总和），然后在表中找到最大值，使得D(x,n) = true。

- amit

---

你的例子是正确的。明白了。然而，虽然你的方法听起来是正确的，但我仍然无法完全理解它。你能否附加更多关于D(x,i)是什么以及true和false代表什么的描述？ - John Lui

@JohnLui D(x,i) 表示您可以使用前 i 个元素从中获取总和为 x 的子集。这意味着，D(SUM/2,n) 意味着列表中存在一个大小为 SUM/2 的子集，其中包含任何元素。 - amit

@amit 这如何确保平均分配？n/2 n/2？ - CoderBC

为了确保等分，您需要向递归公式添加一个维度，该维度包括所选元素的数量。它将增加*n乘数到复杂度中，使其变为O(SUM*n^2)而不是O(SUM*n)。 - amit

Answer 2

问题是SubSet Sum问题的特化版本，该问题决定我们是否可以找到任何两个分区具有相等的总和。这是一个NP完全问题。

但是，所讨论的问题要求找到两个相等的分区，其中满足以下两个条件时平等保持：

分区的大小最多相差1； 分区中元素的总和最小； 当然，在这里我们要求对更普遍的NP完全问题的次优解。

例如，对于A=[1，2，3，4，5，6，7，8，9]，我们可以有这样的两个分区{[1，3，2，7，9]，[5，4，6，8]}，其差值= abs（22-23）= 1。

我们的目标是找到具有最佳逼近比的次优解。想法是将数组分为元素对，以尽可能均匀地分配总和到分区中。因此，每次我们都会尝试取2个对，并将一个对放在一个分区中，另一个对放在另一个分区中。

对数组进行排序 如果元素数量小于4，则根据数组中有1个元素、2个元素或3个元素的情况创建相应的分区。 否则，我们每次取两个成对元素并将它们放入两个分区中，以使它们的差最小。 从排序后的数组中选择一对（最大和最小）元素，并将其放入较小的（相对于总和）分区中。 然后选择第二大的元素并找到它的伙伴，将它们放入“其他”分区中，以使第二大元素和它的伙伴的总和最小化分区之间的差异。 上述方法将给出一个次优解。该问题是NP完全问题，因此我们无法得到最优解，但可以通过以下方式改善近似比率。 如果我们有次优解（即sum diff != 0），则我们尝试通过交换较大分区中的大元素和较小分区中的小元素来改善解决方案，以使交换实际上最小化了sum diff。 以上方法的O(n^2)时间和O(n)空间实现如下：

//overall O(n^2) time and O(n) space solution using a greedy approach


----------


----------


----------



     public static ArrayList<Integer>[] findEqualPartitionMinSumDif(int A[]){
    //first sort the array - O(nlgn)
    Arrays.sort(A);
    ArrayList<Integer> partition1 = new ArrayList<Integer>();
    ArrayList<Integer> partition2 = new ArrayList<Integer>();

    //create index table to manage largest unused and smallest unused items
    //O(n) space and O(nlgn) time to build and query the set
    TreeSet<Integer> unused = new TreeSet<>();
    for(int i = 0; i<A.length; i++){
        unused.add(i);
    }

    int i = 0;
    int j = A.length-1;
    int part1Sum = 0;
    int part2Sum = 0;
    int diffSum = 0;

    //O(n^2) processing time
    while(unused.size() > 0){
        i = unused.first();
        j = unused.last();
        diffSum = part1Sum-part2Sum;

        //in case of size of the array is not multiple of 4 then we need to process last 3(or 2 or 1)
        //element to assign partition. This is special case handling
        if(unused.size() < 4){
            switch(unused.size()){
                case 1: 
                    //put the 1 remaining item into smaller partition
                    if(diffSum > 0){
                        partition2.add(A[i]);
                        part2Sum += A[i];
                    }
                    else{
                        partition1.add(A[i]);
                        part1Sum += A[i];
                    }
                break;
                case 2:
                    //among the remaining 2 put the max in smaller and min in larger bucket
                    int max = Math.max(A[i], A[j]);
                    int min = Math.min(A[i], A[j]);
                    if(diffSum > 0){
                        partition2.add(max);
                        partition1.add(min);
                        part2Sum += max;
                        part1Sum += min;
                    }
                    else{
                        partition1.add(max);
                        partition2.add(min);
                        part1Sum += max;
                        part2Sum += min;
                    }
                break;
                case 3:
                    //among the remaining 3 put the two having total value greater then the third one into smaller partition
                    //and the 3rd one to larger bucket 
                    unused.remove(i);
                    unused.remove(j);
                    int middle = unused.first();

                    if(diffSum > 0){
                        if(A[i]+A[middle] > A[j]){
                            partition2.add(A[i]);
                            partition2.add(A[middle]);
                            partition1.add(A[j]);
                            part2Sum += A[i]+A[middle];
                            part1Sum += A[j];
                        }
                        else{
                            partition2.add(A[j]);
                            partition1.add(A[i]);
                            partition1.add(A[middle]);
                            part1Sum += A[i]+A[middle];
                            part2Sum += A[j];
                        }
                    }
                    else{
                        if(A[i]+A[middle] > A[j]){
                            partition1.add(A[i]);
                            partition1.add(A[middle]);
                            partition2.add(A[j]);
                            part1Sum += A[i]+A[middle];
                            part2Sum += A[j];
                        }
                        else{
                            partition1.add(A[j]);
                            partition2.add(A[i]);
                            partition2.add(A[middle]);
                            part2Sum += A[i]+A[middle];
                            part1Sum += A[j];
                        }
                    }
                break;
                default:
            }

            diffSum = part1Sum-part2Sum;
            break;
        }

        //first take the largest and the smallest element to create a pair to be inserted into a partition
        //we do this for having a balanced distribute of the numbers in the partitions
        //add pair (i, j) to the smaller partition 
        int pairSum = A[i]+A[j];
        int partition = diffSum > 0 ? 2 : 1;
        if(partition == 1){
            partition1.add(A[i]);
            partition1.add(A[j]);
            part1Sum += pairSum;
        }
        else{
            partition2.add(A[i]);
            partition2.add(A[j]);
            part2Sum += pairSum;
        }

        //update diff
        diffSum = part1Sum-part2Sum;
        //we have used pair (i, j)
        unused.remove(i);
        unused.remove(j);
        //move j to next big element to the left
        j = unused.last();
        //now find the buddy for j to be paired with such that sum of them is as close as to pairSum
        //so we will find such buddy A[k], i<=k<j such that value of ((A[j]+A[k])-pairSum) is minimized.
        int buddyIndex = unused.first();
        int minPairSumDiff = Integer.MAX_VALUE;
        for(int k = buddyIndex; k<j; k++){
            if(!unused.contains(k))
                continue;

            int compPairSum = A[j]+A[k];
            int pairSumDiff = Math.abs(pairSum-compPairSum);

            if(pairSumDiff < minPairSumDiff){
                minPairSumDiff = pairSumDiff;
                buddyIndex = k;
            }
        }

        //we now find buddy for j. So we add pair (j,buddyIndex) to the other partition
        if(j != buddyIndex){
            pairSum = A[j]+A[buddyIndex];
            if(partition == 2){
                partition1.add(A[j]);
                partition1.add(A[buddyIndex]);
                part1Sum += pairSum;
            }
            else{
                partition2.add(A[j]);
                partition2.add(A[buddyIndex]);
                part2Sum += pairSum;
            }

            //we have used pair (j, buddyIndex)
            unused.remove(j);
            unused.remove(buddyIndex);
        }
    }

    //if diffsum is greater than zero then we can further try to optimize by swapping 
    //a larger elements in large partition with an small element in smaller partition
    //O(n^2) operation with O(n) space
    if(diffSum != 0){
        Collections.sort(partition1);
        Collections.sort(partition2);

        diffSum = part1Sum-part2Sum;
        ArrayList<Integer> largerPartition = (diffSum > 0) ? partition1 : partition2;
        ArrayList<Integer> smallerPartition = (diffSum > 0) ? partition2 : partition1;

        int prevDiff = Math.abs(diffSum);
        int largePartitonSwapCandidate = -1;
        int smallPartitonSwapCandidate = -1;
        //find one of the largest element from large partition and smallest from the smaller partition to swap 
        //such that it overall sum difference in the partitions are minimized
        for(i = 0; i < smallerPartition.size(); i++){
            for(j = largerPartition.size()-1; j>=0; j--){
                int largerVal = largerPartition.get(j);
                int smallerVal = smallerPartition.get(i);

                //no point of swapping larger value from smaller partition
                if(largerVal <= smallerVal){
                    continue;
                }

                //new difference if we had swapped these elements
                int diff = Math.abs(prevDiff - 2*Math.abs(largerVal - smallerVal));
                if(diff == 0){
                    largerPartition.set(j, smallerVal);
                    smallerPartition.set(i, largerVal);
                    return new ArrayList[]{largerPartition, smallerPartition};
                }
                //find the pair to swap that minimizes the sum diff
                else if (diff < prevDiff){
                    prevDiff = diff;
                    largePartitonSwapCandidate = j;
                    smallPartitonSwapCandidate = i;
                }
            }
        }

        //if we indeed found one such a pair then swap it. 
        if(largePartitonSwapCandidate >=0 && smallPartitonSwapCandidate >=0){
            int largerVal = largerPartition.get(largePartitonSwapCandidate);
            int smallerVal = smallerPartition.get(smallPartitonSwapCandidate);
            largerPartition.set(largePartitonSwapCandidate, smallerVal);
            smallerPartition.set(smallPartitonSwapCandidate, largerVal);
            return new ArrayList[]{largerPartition, smallerPartition};
        }
    }

    return new ArrayList[]{partition1, partition2};
}

- Vaibhav Varshney

---

Copied: http://www.zrzahid.com/equal-partitioning-with-minimum-difference-in-sum/ - Rajat Mishra