拔河

题目描述

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

输入格式

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

输出

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

样例输入

3
100
90
200

样例输出

190 200

分析，即为01背包问题，背包容量为总重量的一半

//拔河
#include<stdio.h>  
#include<string.h>  
int max(int a,int b)  
{  
    return a>b?a:b;  
}  
int main()  
{  
    int n,i,j,sum,a[110],dp[500000];  
    while(scanf("%d",&n)!=EOF)  
    {  
        sum=0;  
        memset(dp,0,sizeof(dp));  
        for(i=1; i<=n; i++)  
        {  
            scanf("%d",&a[i]);  
            sum+=a[i];  
        }  
        for(i=1; i<=n; i++)  
        {  
            for(j=sum/2; j>=0; j--)  
            {  
                if(j>=a[i])  
                {  
                    dp[j]=max(dp[j],dp[j-a[i]]+a[i]);  
                }  
            }  
        }  
        printf("%d %d\n",dp[sum/2],sum-dp[sum/2]);  
    }  
    return 0;  
}   

拔河,布布扣,bubuko.com

拔河

原文：http://blog.csdn.net/u013240812/article/details/21283483