d390. 00562 - Dividing coins -- UVa562 | From: [203.72.60.250] | 發表日期 : 2011-04-21 12:51

#include<iostream>

using namespace std;

int main (){

    int s[100];

    int t, m,half,total;

    int *c;

    while(cin>>t){

       for(int i=1;i<=t;i++){

            cin>>m; 

            total=0;  

            for(int i=1;i<=m;i++){

                    cin>>s[i];

                    total+=s[i]; 

                    }   

            half=total/2;

            c=new int[half+1];

            for(int i=0;i<=half;i++)c[i]=0;

            for(int i=1;i<=m;i++)

                for(int j=half;j>=1;j--){

                    if(s[i]<=j){

                          if(c[j]<=c[j-s[i]])c[j]=c[j-s[i]]+s[i];                       

                                }                              

                        }

               cout<< total-2*c[half]<<endl;                      

               delete[]c;

               }                

                  }    

    return 0;  

    }