zb的生日
时间限制：
3000 ms | 内存限制：
65535 KB
难度：
2
- 描述
-
今天是阴历七月初五，acm队员zb的生日。zb正在和C小加、never在武汉集训。他想给这两位兄弟买点什么庆祝生日，经过调查，zb发现C小加和never都很喜欢吃西瓜，而且一吃就是一堆的那种，zb立刻下定决心买了一堆西瓜。当他准备把西瓜送给C小加和never的时候，遇到了一个难题，never和C小加不在一块住，只能把西瓜分成两堆给他们，为了对每个人都公平，他想让两堆的重量之差最小。每个西瓜的重量已知，你能帮帮他么？
- 输入
-
多组测试数据（<=1500）。数据以EOF结尾
第一行输入西瓜数量N (1 ≤ N ≤ 20)
第二行有N个数，W1, …, Wn (1 ≤ Wi ≤ 10000)分别代表每个西瓜的重量 - 输出
- 输出分成两堆后的质量差
- 样例输入
-
5 5 8 13 27 14
- 样例输出
-
3
#include<stdio.h> #include<math.h> int T, total, ans, sum; int ch[21]; void dfs(int cur, int sum) { if(T== cur) return; int t; t=(int)fabs(total-sum-sum); if(t < ans) ans = t; dfs(cur+1, sum); dfs(cur+1, sum+ch[cur]); } int main() { int i; while(scanf("%d", &T)!=EOF) { total = 0; for(i=0;i<T;i++) { scanf("%d", &ch[i]); total += ch[i]; } ans = 0x7FFFFFFF; dfs(0, 0); if(T==0) printf("0\n"); else printf("%d\n", ans); } return 0; } //TLE #include<stdio.h> #include<math.h> #include<string.h> int min, sum, total, n; int weight[25]; int vis[25]; void get_next(int cur, int n, int a[]) { if(cur == n) { if(min > (int)fabs(total - 2 * sum)) min = (int)fabs(total - 2 * sum); return; } get_next(cur + 1, n, a); for(int i = 0; i < n; i++) { if(!vis[i]) { vis[i] = 1; sum += a[i]; get_next(cur + 1, n, a); sum -= a[i]; vis[i] = 0; } } } int main() { int i; while(scanf("%d", &n) != EOF) { total = 0; memset(vis, 0, sizeof(vis)); for(i = 0; i < n; i++) { scanf("%d", &weight[i]); total += weight[i]; } sum = 0; min = 200001; get_next(0, n, weight); printf("%d\n", min); } return 0; } //01背包TLE #include<stdio.h> #include<string.h> int main() { int T,i,j;int sum; int ch[21],d[100001]; while(scanf("%d",&T)!=EOF) { sum=0; memset(d,0,sizeof(d));//ch没必要 for(i=1;i<=T;i++) { scanf("%d",ch+i); sum+=ch[i]; } //temp=(sum+1)/2; for(i=1;i<=T;i++) for(j=(sum+1)/2;j>=ch[i];j--) if(d[j]<d[j-ch[i]]+ch[i]) d[j]=d[j-ch[i]]+ch[i]; printf("%d\n",sum-2*d[temp]); } return 0; } //停止 #include<stdio.h> #include<string.h> int T; int visit[21],ch[21]; void dfs(int ans,int sum) { int i,j,k,temp; temp=(sum+1)/2; if(ans<temp&&ans+ch[i-1]>temp&&i==T) printf("%d\n",sum-2*ans); else for(i=1;i<=T;i++) if(!visit[i-1]) { ans+=ch[i-1]; visit[i]=1; if(ans>temp) { dfs(ans-ch[i-1],sum); visit[i-1]=0; } } } int main() { int i,j;int sum; int d[100001]; while(~scanf("%d",&T)) { sum=0; memset(d,0,sizeof(d));//ch没必要 memset(visit,0,sizeof(visit)); for(i=1;i<=T;i++) { scanf("%d",ch+i); sum+=ch[i]; } dfs(0,sum); } return 0; }
