题目链接：

题意：从n个数中选出一些数，将选出的数分成两个集合，使得这两个集合的数字之和相等。求和最大为多少？

思路：f[i][j]表示前i个数构成两个差为j的集合，这两个集合的数字之和（ 注意是这两个集合一起的数字之和）

最大为f[i][j]。则答案就是f[n][0]/2。具体实现时用滚动数组。。。真的不好想啊，看了别人的才知道的。。

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #define max(x,y) ((x)>(y)?(x):(y)) 5 #define min(x,y) ((x)<(y)?(x):(y)) 6 using namespace std; 7  8 int C,num=0; 9 int n,a[55],f[2][250005],sum;10 11 int abs(int x)12 {13     return x>0?x:-x;14 }15 16 int DP()17 {18     memset(f,-1,sizeof(f));19     int cur=1,pre=0,i,j,k,t=0;20     f[0][0]=0;21     for(i=0;i
         
          >1;41 }42 43 44 int main()45 {46     for(scanf("%d",&C);C--;)47     {48         scanf("%d",&n);49         int i;50         sum=0;51         for(i=0;i
          
           >=1;53         printf("Case %d: ",++num);54         int ans=DP();55         if(ans==0) puts("impossible");56         else printf("%d\n",ans);57     }58     return 0;59 }