一句话题意:$n$ 个正整数分成两组,使得两组总和的差最小,先输出较大的和再输出较小的,$n\le 1000$ ,每个正整数 $\le 10^6$ 。
老实说,我个人非常不喜欢这种NP-Complete问题再加上一个剪枝搜索,因为这种东西的复杂度始终是 $O(玄学)$ ,而且搜索的上界始终是 $O(2^n)$ ,所以这种题一出就很容易出假,而且无法排除各种hack数据卡爆搜索策略的可能性。
虽然考虑01背包状态我们可以用bitset
,但是这题值域上限是 $10^9$ 开不了那么大的空间,所以只能暴搜+剪枝了。令人头疼…
但是我这里还是给出一个比较快的搜索方式,至少目前的11组数据可以各在1ms就跑完。
首先先对数组从小到大排序。然后实时记录当前搜索到的较大和的最小可能值(初始状态是所有元素的和),由于要尽可能减少搜索步数,我们直接从大到小来进行搜索,搜索分支就是选当前数或者不选当前数。剪枝的第一个关键条件就是如果当前搜索的较大和大于等于已经搜索到的最小可能值,直接剪枝;另一个关键条件就是:如果答案正好搜到了总和的一半,又或者是总和一半+1或-1,那么此时就直接是最优解,直接停机。 然后注意一下这种情况有可能搜索出来的是较小的那个解(总和一半-1),特判一下再输出就行了。
另外还有一种特殊情况,如果最大的数已经大于等于总和的一半,那他自己就是那个较大的集合,直接输出答案就行了。
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 1005;
int n, x;
int a[N], sum;
int subset;
bool finished;
void dfs(int subsum, int pos)
{
if (pos < 0 || finished)
return;
if (subsum >= subset)
return;
if (subsum >= (sum >> 1))
{
subset = min(subset, subsum);
if (subset == (sum >> 1))
finished = 1;
return;
}
dfs(subsum + a[pos], pos - 1);
dfs(subsum, pos - 1);
}
int main()
{
while (scanf("%d", &x) != EOF)
a[++n] = x, sum += a[n];
sort(a + 1, a + n + 1);
if (a[n] >= (sum >> 1))
return printf("%d %d\n", a[n], sum - a[n]), 0;
else
subset = sum, dfs(0, n), printf("%d %d\n", max(subset, sum - subset), min(subset, sum - subset));
}