Code: Select all

```
//C++
#include<iostream>
#include<algorithm>
using namespace std;
#define max_(a,b)(a>b?a:b)
int a[110];
int mark[10000][10000];
int store[10000][10000];
int n,t;
int dp(int i, int w)
{
if(i==0 || w==0)
return 0;
else if(mark[i][w]==t)
return store[i][w];
int res;
if(a[i]<=w)
{
res=max_(dp(i-1,w),dp(i-1,w-a[i])+a[i]);
}
else
res=dp(i-1,w);
mark[i][w]=t;
store[i][w]=res;
return res;
}
int main()
{
int i,w,cs,tt,sum,x;
//freopen("1.txt","r",stdin);
cin>>tt;
for(cs=1;cs<=tt;cs++)
{
t++;
cin>>n;
sum=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
w=sum/2;
x=dp(n,w);
printf("%d\n",(sum-2*x));
}
}
```

plz...