游客 注册 | 登录
中文 | En

4015 - 数划分问题

通过次数

0

提交次数

0

时间限制 : 10 秒 内存限制 : 128 MB

给定n个正整数的集合S，把S划分成两个不相交的自给S1和S2，使得差异 E(S) = |sum(S1) - sum(S2)| 最小，其中sum(Si)是Si中元素之和。设计一个穷举搜索算法求解该问题。

题目输入

输入包括多组数据。每组数据的第一行是一个整数n (10 <= n <= 20)代表集合的大小。n = 0意味着输入结束。接下来有n行，每一行一个整数代表集合的元素。

题目输出

对于每组测试数据，输出划分集合得到的两个子集元素和的最小差异。

输入/输出样例

输入格式

10
205
157
133
111
100
91
88
59
47
23
8
635
853
401
868
335
435
704
754
0

输出格式

0
3

C语言解答

#include <stdio.h>
#include <math.h>

int main()
{
	int i, j;
	int n;
	int a[1000];
	int f[100000];
	int sum;
	int min;

	scanf("%d", &n);
	while (n > 0)
	{
		sum = 0;
		for (i = 0; i < n; i++)
		{
			scanf("%d", &a[i]);
			sum += a[i];
		}

		f[0] = 1;
		for (j = 1; j < sum; j++)
			f[j] = 0;
		for (i = 0; i < n; i++)
			for (j = sum; j >= a[i]; j--)
				if (f[j - a[i]])
					f[j] = 1;

		min = 100000;
		for (j = 1; j < sum; j++)
			if (f[j])
				if (abs(j - (sum - j)) < min)
					min = abs(j - (sum - j));

		printf("%d\n", min);

		scanf("%d", &n);
	}

	return 1;
}
请先登陆