游客 注册 | 登录
中文 | En

1095 - 拔河

通过次数

0

提交次数

0

时间限制 : 3 秒 内存限制 : 32 MB

小明班里要举行一次拔河比赛，班主任决定将所有人分为两队，每个人都必须参加。两个队伍的人数之差不能超过1，并且两个队伍的体重之和要尽可能相近，当然相同是最好的了。

题目输入

输入包含多组测试数据。
每组输入的第一行是一个正整数n（2<=n<=100），表示共有n个人。
接下来n行，每行输入一个整数w（1<=w<=450），表示每个人的体重。

题目输出

对于每组输入，分别输出两个队伍的体重之和，按升序排序。

输入/输出样例

输入格式

3
100
90
200

输出格式

190 200

C语言解答

#include<stdio.h>
#include<string.h>

int n,sum,dp[55][45010];

int abs(int x)
{
	return x>0?x:-x;
}

void add(int x)
{
	int i,j;
	for(i=n/2-1;i>=0;i--)
	{
		for(j=0;j<=sum;j++)
		{
			if(dp[i][j])
			{
				if(j+x<45010)
					dp[i+1][j+x]=1;
			}
		}
	}
}
 
int main()
{
	int i,a,ans;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a);
			sum+=a;
			add(a);
        }
		ans=sum;
		for(i=0;i<=sum;i++)
		{
			if(dp[n/2][i])
			{
				if(abs(sum-i-i)<ans)
					ans=abs(sum-i-i);
			}
		}
		printf("%d %d\n",(sum-ans)/2,(sum-ans)/2+ans);
	}
	return 0;
}

C++解答

#include<stdio.h>
#include<string.h>

int n,sum,dp[55][45010];

int abs(int x)
{
	return x>0?x:-x;
}

void add(int x)
{
	int i,j;
	for(i=n/2-1;i>=0;i--)
	{
		for(j=0;j<=sum;j++)
		{
			if(dp[i][j])
			{
				if(j+x<45010)
					dp[i+1][j+x]=1;
			}
		}
	}
}
 
int main()
{
	int i,a,ans;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;
		memset(dp,0,sizeof(dp));
		dp[0][0]=1;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a);
			sum+=a;
			add(a);
        }
		ans=sum;
		for(i=0;i<=sum;i++)
		{
			if(dp[n/2][i])
			{
				if(abs(sum-i-i)<ans)
					ans=abs(sum-i-i);
			}
		}
		printf("%d %d\n",(sum-ans)/2,(sum-ans)/2+ans);
	}
	return 0;
}

Java解答

import java.util.Scanner;


public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNextInt()) {
			int n = in.nextInt();
			int[] w = new int[n + 1];
			int sum = 0;
			for (int i = 1; i <= n; i++) {
				w[i] = in.nextInt();
				sum += w[i];
			}
			int ave = sum / 2;
			int[] f = new int[ave + 1];
			for (int i = 1; i <= n; i++) {
				for (int j = ave; j >= w[i]; j--) {
					f[j] = Math.max(f[j], f[j - w[i]] + w[i]);
				}
			}
			int t1 = f[ave];
			int t2 = sum - f[ave];
			if (t1 <= t2)
				System.out.println(t1 + " " + t2);
			else
				System.out.println(t2 + " " + t1);
		}
	}
}
请先登陆