南阳理工OJ 456 邮票分你一半 差最小的两分

#include<stdio.h>
#include<string.h>
int w[1005];
bool f[50010];
int totle;
int ave;
int main()
{
    int T;
    int n,i,j;
    scanf("%d",&T);
    while(T--)
    {
        memset(f,0,sizeof(f));
        f[0]=true;
        scanf("%d",&n);
        for(i=0,totle=0;i<n;i++)
        {
            scanf("%d",&w[i]);
            totle+=w[i];
        }
        ave=totle>>1;
        for(i=0;i<n;i++)
            for(j=ave;j>=w[i];j--)
                if(f[j-w[i]])f[j]=true;
        while(!f[ave])ave--;
        printf("%d\n",totle-2*ave);
    }
    return(0);
}

 

 

 

#include <stdio.h>
#define max(a,b) a>b?a:b
int V,ans,n,w[1001],sum[1001];
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 m;
	scanf("%d",&m);
	while(m--){
		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;
}