如何将一个集合分成两个子集，使两个集合中的数字之和的差值最小？
给定一组数字，将这些数字分成两个子集，使得两个子集中的数字之和的差异最小。
这是我的想法，但我不确定这是不是一个正确的解决方案：
- 对数组进行排序，
- 取前两个元素。假设它们是2个集合(每个集合有1个元素)，
- 从数组中获取下一个元素。
- 决定这个元素应该放在哪个集合中(通过计算=>，它应该是minimum)
- Repeat
这是正确的解决方案吗？我们能做得更好吗？
回答 19
Stack Overflow用户
发布于 2011-07-06 21:45:51
您所描述的问题的decision版本是NP-complete问题，称为。在许多情况下，有许多approximations提供最佳或至少足够好的解决方案。
你描述的简单算法是游乐场孩子们选择团队的一种方式。如果集合中的数字具有相似的数量级，则该greedy algorithm表现得非常好。
“美国科学家”的文章对这个问题进行了很好的分析。你应该通读一遍！
Stack Overflow用户
发布于 2011-07-06 21:29:15
不，那不管用。没有多项式时间解(除非是P=NP)。你能做的最好的事情就是查看所有不同的子集。看一看subset sum problem。
考虑一下列表[0, 1, 5, 6]。你会声称是{0, 5}和{1, 6}，而最好的答案实际上是{0, 1, 5}和{6}。
Stack Overflow用户
发布于 2019-05-20 23:20:45
不，你的算法是错的。你的算法遵循贪婪的方法。我实现了你的方法，它在这个测试用例上失败了：(你可以试试here)
贪婪算法：
#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贪心算法失败的原因是，当在当前较大的和集中取较大的元素时，它没有考虑到这种情况，然后在较大的和集中取较小的元素可能会得到更好的结果。它总是试图最小化当前差异，而不探索或了解更多可能性，而在正确的解决方案中，您可能会在较大的集合中包括一个元素，并在以后包括一个小得多的元素来补偿这种差异，这与上面的测试用例中的情况相同。
正确的解决方案：
要了解解决方案，您需要了解以下所有问题：
我的代码(逻辑与this相同)：
#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;
}https://stackoverflow.com/questions/6597180
复制相似问题