拔河_牛客博客

拔河

时间限制: 3 Sec 内存限制: 32 MB
</center>

题目描述

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

输入

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

输出

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

样例输入

样例输出

190 200

解题思路

dp题，直接找状态转移方程，水题。直接见代码：

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