劉得恩

1. #include<cstdio>
   
2. #include<cstring>
   
3. void print(bool*A,int n)
   
4. {
   
5.     for(int i=0;i<n;i++)
   
6.         printf("%d ",A[i]);
   
7.     puts("");
   
8. }
   
9. int main()
   
10. {
    
11.     bool dp[101000];
    
12.     int t,lemon[105],n;
    
13.     while(scanf("%d",&n)==1)
    
14.     {
    
15.         while(n--)
    
16.         {
    
17.             int sum=0;
    
18.             scanf("%d",&t);
    
19.             for(int i=0; i<t; i++)
    
20.             {
    
21.                 scanf("%d",&lemon[i]);
    
22.                 sum+=lemon[i];
    
23.             }
    
24.             int h=sum/2,dpsum=0;
    
25.             memset(dp,false,sizeof(dp));
    
26.             dp[0]=true;
    
27.             for(int i=0; i<t; i++)
    
28.             {
    
29.                 for(int j=dpsum; j>=0; j--)
    
30.                     if(dp[j])dp[j+lemon[i]]=true;
    
31.                 dpsum+=lemon[i];
    
32.             }
    
33.             //print(dp,sum);
    
34.             int u;
    
35.             for(u=h;; u--)if(dp[u])break;
    
36.             printf("%d\n",sum-u);
    
37.         }
    
38.     }
    
39.     return 0;
    
40. }

複製代碼