如何将一组分成两个子集,使两组数字之和的差异最小？

Question

给定一组数字,将数字划分为两个子集,使得两个子集中的数字之和之间的差异最小.

这是我的想法,但我不确定这是否是一个正确的解决方案:

1. 对数组进行排序
2. 采取前两个元素.将它们视为2组(每组有1个元素)
3. 从数组中获取下一个元素.
4. 决定该元素应该在哪个集合中(通过计算sum =>它应该是最小的)
5. 重复

这是正确的解决方案吗？我们可以做得更好吗？

Answer 1

您描述的问题的决策版本是NP完全问题,它被称为分区问题.在许多情况下,有许多近似值提供了最佳或至少足够好的解决方案.

您描述的简单算法是孩子们选择团队的方式.如果集合中的数字具有相似的数量级,则该贪婪算法表现得非常好.

文章最简单的最困难的问题,由美国科学家,给出了问题的一个很好的分析.你应该通过阅读它!

Answer 2

不,那不行.没有多项式时间解决方案(除非P = NP).您可以做的最好的事情就是查看所有不同的子集.看看子集求和问题.

考虑清单[0, 1, 5, 6].你会要求{0, 5}和{1, 6},当最好的答案居然是{0, 1, 5}和{6}.

Answer 3

不，你的算法是错误的。你的算法遵循贪婪的方法。我实现了你的方法，但在这个测试用例中失败了：（你可以在这里尝试）

贪心算法：

#include<bits/stdc++.h>
#define rep(i,_n) for(int i=0;i<_n;i++)
using namespace std;

#define MXN 55
int a[MXN];

int main() {
    //code
    int t,n,c;
    cin>>t;
    while(t--){
        cin>>n;
        rep(i,n) cin>>a[i];
        sort(a, a+n);
        reverse(a, a+n);
        ll sum1 = 0, sum2 = 0;
        rep(i,n){
            cout<<a[i]<<endl;
            if(sum1<=sum2) 
                sum1 += a[i]; 
            else 
                sum2 += a[i]; 
        }
        cout<<abs(sum1-sum2)<<endl;
    }
    return 0;
}

测试用例：

1
8 
16 14 13 13 12 10 9 3

Wrong Ans: 6
16 13 10 9
14 13 12 3

Correct Ans: 0
16 13 13 3
14 12 10 9

贪心算法失败的原因是，它没有考虑在当前较大和集中取较大元素而稍后在较大和集中取小得多的元素可能会产生更好结果的情况。它总是尝试最小化当前差异，而不探索或了解进一步的可能性，而在正确的解决方案中，您可能会在更大的集合中包含一个元素，并稍后包含一个更小的元素来补偿这种差异，与上面的测试用例相同。

正确的解决方案：

要理解该解决方案，您需要按顺序理解以下所有问题：

• 0/1 背包动态规划
• 用 DP 划分相等子集和
• 解决方案

我的代码（与此相同的逻辑）：

#include<bits/stdc++.h>
#define rep(i,_n) for(int i=0;i<_n;i++)
using namespace std;

#define MXN 55
int arr[MXN];
int dp[MXN][MXN*MXN];

int main() {
    //code
    int t,N,c;
    cin>>t;
    while(t--){
        rep(i,MXN) fill(dp[i], dp[i]+MXN*MXN, 0);

        cin>>N;
        rep(i,N) cin>>arr[i];
        int sum = accumulate(arr, arr+N, 0);
        dp[0][0] = 1;
        for(int i=1; i<=N; i++)
            for(int j=sum; j>=0; j--)
                dp[i][j] |= (dp[i-1][j] | (j>=arr[i-1] ? dp[i-1][j-arr[i-1]] : 0));

        int res = sum;

        for(int i=0; i<=sum/2; i++)
            if(dp[N][i]) res = min(res, abs(i - (sum-i)));

        cout<<res<<endl;
    }
    return 0;
}