1095 - 拔河
小明班里要举行一次拔河比赛，班主任决定将所有人分为两队，每个人都必须参加。两个队伍的人数之差不能超过1，并且两个队伍的体重之和要尽可能相近，当然相同是最好的了。
Input
输入包含多组测试数据。
每组输入的第一行是一个正整数n（2<=n<=100），表示共有n个人。
接下来n行，每行输入一个整数w（1<=w<=450），表示每个人的体重。
Output
对于每组输入，分别输出两个队伍的体重之和，按升序排序。
Examples
Input
3 100 90 200
Output
190 200
Solution 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; }
Solution 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; }