<span style="font-family: 'Microsoft Yahei'; font-size: 12px; background-color: rgb(245, 245, 245);">题目描述</span>小明班里要举行一次拔河比赛，班主任决定将所有人分为两队，每个人都必须参加。两个队伍的人数之差不能超过1，并且两个队伍的体重之和要尽可能相近，当然相同是最好的了。
输入格式
输入包含多组测试数据。
每组输入的第一行是一个正整数n（2<=n<=100），表示共有n个人。
接下来n行，每行输入一个整数w（1<=w<=450），表示每个人的体重。
输出
对于每组输入，分别输出两个队伍的体重之和，按升序排序。
样例输入
3
100
90
200
样例输出
190 200
我的理解:
1.总共有n个人，将之分为2部分,差值为1，或者零，如果，n是奇数的话,只能分为n/2+1,n/2个，否则是偶数只能分为两部分相等人数n/2.
2.由于总人数一致每个人的重量已知，如果知道一个队伍中的总重量，那么可以通过所有人的总重量-该部分人的总重量.的出另一个队伍人的总重量.
3.由于要使差值最小，那么两部分人应该尽量接近所有人重量的平均值.
4.dp[i][j]为选择到第i个人时，是否可以是队伍人数总重量达到j.
dp[i][j]=dp[i-1][j-a[i]];
#include <stdio.h>
#include <string.h>
#define maxn 500+1
int dp[55][55*510]={0};
int p[maxn]={0};
void swap(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}
int min(int a,int b){
return a<b?a:b;
}
int main(){
int n,i,maxv=0,nn;
int _max,_min;
int flag=0;
while(scanf("%d",&n)!=EOF){
memset(dp,0,sizeof(dp));
maxv=0;
flag=0;
for(i=0;i<n;i++){
scanf("%d",&p[i]);
maxv+=p[i];
}
nn=n%2?n/2:n/2-1;
for(i=0;i<n;i++){//选到的人数.
int j;
for(j=min(nn,i);j>=0;j--){//已经选的人数
int k;
for(k=maxv/2;k>=0;k--){//总共的重量
if(j>0){
if(k-p[i]>=0){
if(dp[j][k]==0)
dp[j][k]=dp[j-1][k-p[i]];
}
}else{
if(dp[j][k]==0)
dp[j][k]=(k==p[i]?1:0);
}
}
}
}
for(i=maxv/2;i>=0;i--){
if(dp[nn][i]){
_min=i;
_max=maxv-_min;
flag=1;
break;
}
}
if(_min>_max)
swap(&_min,&_max);
printf("%d %d\n",_min,_max);
}
return 0;
}