nyoj 325 zb的生日（dfs）

缺乏、安全感 2024-02-17 20:51 48阅读 0赞

### 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

分析：数据量比较小，dfs可以搜出来，另外可以用０１背包求解

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define INF 1000000
    int a[23];
    int n;
    int sum;
    int Min;
    void dfs(int cur,int pos){    //当前和、以及位置（-1表示刚开始） 
    	if(sum%2==0 && cur==sum/2){
    		Min=0;
    		return ;
    	}
    	if(cur<=sum/2)Min=min(Min,sum-2*cur);
    	
    	for(int i=pos+1;i<n;i++){
    		if(cur+a[i]>sum/2)continue;  //剪枝 
    		dfs(cur+a[i],i);
    	}
    }
    int main(){
    	while(scanf("%d",&n)==1){
    		sum=0;
    		Min=INF;
    		for(int i=0;i<n;i++)
    		{
    		scanf("%d",&a[i]);
    		sum+=a[i];
    		}
    		
    		dfs(0,-1);
    		
    		printf("%d\n",Min);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，48人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj1190（dfs+剪枝）生日蛋糕

生日蛋糕 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

柔光的暖阳◎/ 2024年02月17日 23:55/ 0 赞/ 84 阅读

相关 nyoj 325 zb的生日（dfs）

zb的生日时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述今天是阴历七月初五，acm队员zb的生日。zb正在和C小加、never在

缺乏、安全感/ 2024年02月17日 20:51/ 0 赞/ 49 阅读

相关 Poj 1190 生日蛋糕 (DFS 剪枝)

隐约记得前几年网络赛有过类似的题，当时毫无想法…… 参考了：http://blog.csdn.net/lencle/article/details/7016191 可能还能

ゞ浴缸里的玫瑰/ 2022年09月20日 13:00/ 0 赞/ 188 阅读

相关 NYOJ 312 20岁生日

20岁生日时间限制： 1000 ms | 内存限制： 65535 KB 难度： 1 描述路过这的20岁生日就要到了，他当然很开心，可是他突然想到一个问题，是不是

短命女/ 2022年08月25日 01:39/ 0 赞/ 202 阅读

相关 NYOJ 488-素数环【dfs】

素数环时间限制：1000 ms | 内存限制：65535 KB 难度：2 描述有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都

古城微笑少年丶/ 2022年08月21日 11:57/ 0 赞/ 183 阅读

相关 NYOJ 312-20岁生日

20岁生日时间限制： 1000 ms | 内存限制： 65535 KB 难度： 1 描述路过这的20岁生日就要到了，他当然很开心，可是他突然想到一个问题，是不是

古城微笑少年丶/ 2022年08月20日 04:16/ 0 赞/ 193 阅读

相关 nyoj 20 吝啬国度【dfs】

吝啬的国度时间限制：1000 ms | 内存限制：65535 KB 难度：3 描述在一个吝啬的国度里有N个城市，这N个城市间只有N-1条路

男娘i/ 2022年08月18日 01:00/ 0 赞/ 138 阅读

相关ｚｂ的生日

zb的生日时间限制：3000 ms | 内存限制：65535 KB 难度：2 描述今天是阴历七月初五，acm队员zb的生日。zb正在和C小加、neve

墨蓝/ 2022年06月03日 01:17/ 0 赞/ 388 阅读

相关 NYOJ 1276 机器设备【dfs】

机器设备题目描述 > Alpha 公司设计出一种节能的机器设备。它的内部结构是由 N 个齿轮组成。整个机器设备有 > 一个驱动齿轮，当启动它时，它立即按 10

- 日理万妓/ 2022年05月24日 22:12/ 0 赞/ 38 阅读

相关 168. 生日蛋糕（dfs）

题目链接：[https://www.acwing.com/problem/content/170/][https_www.acwing.com_problem_content_

我不是女神ヾ/ 2021年11月09日 09:36/ 0 赞/ 384 阅读