nyoj 325 【zb的生日】

输入

多组测试数据（<=1500）。数据以EOF结尾
第一行输入西瓜数量N (1 ≤ N ≤ 20)
第二行有N个数，W1, …, Wn (1 ≤ Wi ≤ 10000)分别代表每个西瓜的重量

输出

输出分成两堆后的质量差

样例输入

5
5 8 13 27 14

样例输出

3

#include <stdio.h>
#define max(a,b) a>b?a:b
int V,ans,n,w[21],sum[21];
void dfs(int i,int cnt)
{if(i == 0){ans = max(ans,cnt);return ;}if(ans == V || cnt+sum[i] <= ans)      return ;if(cnt+w[i] <= V)dfs(i-1,cnt+w[i]);dfs(i-1,cnt);
}
int main()
{while(~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;
}        

DP

#include<stdio.h>
#include<string.h>
int size[100009];
int main()
{int n;while(scanf("%d",&n)!=EOF){int i,j,sum=0,a[25],m=0;memset(size,0,sizeof(size));size[0]=1;for( i = 0 ; i < n ; ++i){scanf("%d",&a[i]);sum+=a[i];}for(i = 0 ; i < n ; ++ i){if(m!=sum/2)m+=a[i];if(m>sum/2)m=sum/2;for( j = m; j >=a[i] ; j--)if(size[j-a[i]]) size[j]=1;}for(i=sum/2; size[i]==0; i--);printf("%d\n",sum-2*i);}return 0;
}