swustoj-1010: 魔兽争霸之最后的反击

DP

Description

相传人族与兽族对峙了很久，双方均受到了重创，兽族趁人类没有能力发起大规模进攻之时突然袭击，想一次彻底打败人族。人类为了生存，无论老幼伤病，全部参战，兵分两路抗敌。
由于体质不同，我们以血量表示一个人的战斗力，现在给你所有人的血量，请你把人类分成战斗力最接近的两部分。注意，战斗力要最接近，不然，人族会因你而战败呦！

Input

第一行为一个整数n(1<=n<=36)，表示人族的总人数。以下的n行每行一个整数，表示一个人的血量mi（即战斗力），其中1<=mi<=400.

Output

只有一行，包含两个数，即人族的每部分兵的血量总和，较小的一个值放在前面，两个数用空格分隔。

Sample Input

3
20
32
35

Sample Output

35 52

分析：总人数除以二得到平均的一半，这就是背包总容量，再将战斗力尽量装进去……解释的好烂啊反正就是这样，其实就是01背包

• 完整代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int main()
{
    int n,a[1000],i,sum,mid,j,d[1000];
    while(scanf("%d",&n)!=EOF)
    {
        sum=0;
        memset(d,0,sizeof(d));
        memset(a,0,sizeof(a));
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    mid=sum/2;
    for(i=1;i<=n;i++)
    {
        for(j=mid;j>=a[i];j--)
            d[j]=max(d[j-a[i]]+a[i],d[j]);
    }
    printf("%d %d\n",d[mid],sum-d[mid]);
    }
    return 0;
}