[cpp]
描述:把硬幣平分成兩份,尋找與平均數差值最小的就可以
#include <cstdio>
#include <cstring>
bool s[50010];
int num[110];
int main()
{
int n,t,sum,flag,p,m;
// freopen("a.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
sum=flag=m=0;
for(int i=0; i<n; i++)
{
scanf("%d",&num[i]);
sum+=num[i];
}
p=sum/2;
memset(s,false,sizeof(s));
s[0]=true;
for(int i=0; i<n; i++)
{
for(int j=p-1; j>=0; j--)
if(s[j])
{
flag=j+num[i];
if(flag<=p&&!s[flag])
{
s[flag]=true;
if(flag>m) m=flag;
if(m==p) break;
}
}
if(m==p) break;
}
printf("%d\n",sum-2*m);
}
return 0;
}