内存:64  时间:1

题目描述

愚公留下遗愿,让他的两个儿子愚大和愚二完成他移山的愿望:将石头搬出大山。一直以来,愚大背大石头,将小石头留给弟弟愚二背。愚二长大后,想分担哥哥的负担,要求背大石头,让哥哥背小石头。愚大不同意。兄弟二人多次讨论,也不能提出一个公平背石头的方案。

假设有n 块石头,将这n个石头尽可能平分给兄弟二人,即两人分得的石头重量差异最小。请你帮助愚家兄弟解决这个问题。

输入

多组输入,对于每组数据

第一行,一个整数n(3<=n<=1000),表示石头的数目

第二行,n个整数,对于每个整数a[i](1<=a[i]<=50),表示第i块石头的重量

输出

对于每组输入输出两个数 x,y(x<=y) 分别表示两个兄弟背的石头总重量

样例输入

3
1 2 3

样例输出

3 3

提示

代码如下

#include <stdio.h>
#include <string.h>
#define SIZE 1000 * 50

int main() {
	int a[SIZE],d[SIZE],i,j,n,sum;

	while(scanf("%d",&n) != EOF) {
		memset(d,0,sizeof(d));

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

		for(i = 0;i < n;i ++) {
			for(j = sum/2;j >= a[i];j --)
				if(d[j-a[i]] + a[i] > d[j]) d[j] = d[j-a[i]] + a[i];
		}

		printf("%d %d\n",d[sum/2],sum - d[sum/2]);
	}
	return 0;   
}

代码来源于互联网,仅供参考!