knapsack03.cpp

/*************************************
 * Dividing coins UVALive - 5583
 * @author Amirul Islam (shiningflash)
 ************************************/

#include <cstdio>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <list>
#include <iostream>
#include <assert.h>

/**Define memory set function**/
#define mem(x,y) memset(x,y,sizeof(x))
#define CLEAR(x) memset(x,0,sizeof(x))

/**Define function and object**/
#define pb push_back
#define Sort(v) sort(v.begin(),v.end())
#define _sort(s, n) sort(s, s+n)
#define sqr(x) ((x)*(x))

/**Define constant value**/
#define le 50001
#define ERR 1e-9
#define pi (2*acos(0))
#define PI 3.141592653589793

/**Define input**/
#define scanint(a) scanf("%d",&a)
#define scanLLD(a) scanf("%lld",&a)

typedef unsigned long long ll;

using namespace std;

/**********************End*******************/

int coin[le], dp[le];
int t, n, dif;

inline int knapsack(int n, int w) {
    for (int i = 0; i <= w; dp[i] = 0, i++);
    for (int i = 1; i <= n; i++)
        for (int j = w; j > 0; j--)
            if (coin[i] <= j)
                dp[j] = max(coin[i] + dp[j-coin[i]], dp[j]);
    return dp[w];
}

int main() {
    for (scanint(t); t--; ) {
        scanint(n);
        int sum = 0;
        for (int i = 1; i <= n; scanint(coin[i]), sum += coin[i], i++);
        cout << sum - 2 * knapsack(n, sum/2) << endl;
    }
}