题目地址：http://jobdu.sinaapp.com/problem.php?cid=1040&pid=99
C语言源码：
#include<stdio.h>#include<limits.h>#define maxsize 4010#define size 2000int dp[110][maxsize];int max2(int a,int b){ return a>b?a:b;}int max(int a,int b,int c){ return max2(a,b)>c?max2(a,b):c;}int a[1010];int main(){ int t,n,num,i,j,zero; scanf("%d",&t); for(num=1;num<=t;num++) { zero=0; scanf("%d",&n); j=1; for(i=1;i<=n;i++) { scanf("%d",&a[j++]); if(a[j-1]==0) { zero=1; j--; } } n=j-1; for(i=0;i<110;i++) for(j=0;j<maxsize;j++) dp[i][j]=INT_MIN; dp[0][size]=0; for(i=1;i<=n;i++) for(j=0;j<maxsize;j++) if(j-a[i]>=0&&j+a[i]<maxsize) dp[i][j]=max(dp[i-1][j-a[i]]+a[i],dp[i-1][j+a[i]]+a[i],dp[i-1][j]); else { if(j-a[i]<0&&j+a[i]<maxsize) dp[i][j]=max2(dp[i-1][j+a[i]]+a[i],dp[i-1][j]); else if(j+a[i]>=maxsize&&j-a[i]>=0) dp[i][j]=max2(dp[i-1][j-a[i]]+a[i],dp[i-1][j]); else dp[i][j]=dp[i-1][j]; } if(dp[n][size]==0&&zero==0) printf("Case %d: -1\n",num); else printf("Case %d: %d\n",num,dp[n][size]/2); } }