首页 > 代码库 > NYOJ 325 zb的生日

NYOJ 325 zb的生日

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)分别代表每个西瓜的重量
输出
输出分成两堆后的质量差
样例输入
55 8 13 27 14
样例输出
3
来源
ural
上传者
李文鑫


解题:不知道这是什么鸟题,背包居然过不了,还超时。。。。。。。。。我了过去,暴搜就过了。。。。。。。。。。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 #include <climits> 5 using namespace std; 6 int d[25],n,sum,ans; 7 int myabs(int x){ 8     return x < 0 ?-x:x; 9 }10 void dfs(int cur,int add){11     if(cur >= n){12         if(myabs(sum-2*add) < ans) ans = myabs(sum-2*add);13         return;14     }15     dfs(cur+1,add);16     dfs(cur+1,add+d[cur]);17 }18 int main(){19     int i;20     while(~scanf("%d",&n)){21         for(sum = i = 0; i < n; i++){22             scanf("%d",d+i);23             sum += d[i];24         }25         ans = INT_MAX;26         dfs(0,0);27         printf("%d\n",ans);28     }29 }
View Code