NYOJ465

#include<stdio.h>
#include<string.h>

using namespace std;
int dp[50005];
int a[50005];
int main()

{
    int m,n,i,j,score;
    scanf("%d",&m);
    while(m--)
    {
        int sum = 0;
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(i = 0;i < n;i++)
        {
            scanf("%d",&a[i]);
            sum = sum + a[i];
        }
        for(i = 0;i < n;i++)
        {
            for(j = sum / 2;j >= a[i];j--)
            {
                if(dp[j] > dp[j - a[i]] + a[i])
                {
                    dp[j] = dp[j];
                }     // 这个地方非常需要注意如果用if j的限制条件一定是大于等于a[i]
                else
                {
                    dp[j] = dp[j - a[i]] + a[i];
                }
            }
        }
        printf("%d\n",sum - 2 * dp[sum / 2]);
    }
}