描述
小珂最近收集了些邮票,他想把其中的一些给他的好朋友小明。每张邮票上都有分值,他们想把这些邮票分成两份,并且使这两份邮票的分值和相差最小(就是小珂得到的邮票分值和与小明的差值最小),现在每张邮票的分值已经知道了,他们已经分好了,你知道最后他们得到的邮票分值和相差多少吗?
#include <stdio.h>
#define max(a,b) a>b?a:b
int V,ans,n,w[110],sum[110];
void dfs(int i,int cnt)
{
if(i == 0)
{
ans = max(ans,cnt);
return ;
}
if(ans == V || cnt+sum[i] <= ans) //cut
return ;
if(cnt+w[i] <= V)
dfs(i-1,cnt+w[i]);
dfs(i-1,cnt);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
ans = 0;
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
sum[i] = sum[i-1] + w[i];
}
V = sum[n]/2;
dfs(n,0);
printf("%d\n",sum[n]-2*ans);
}
return 0;
}