NYOJ325 zb的生日(01背包，深搜DFS)

本文主要是介绍NYOJ325 zb的生日(01背包，深搜DFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

描述

今天是阴历七月初五，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

代码1（01背包，超时）：

//此代码和 NYOJ邮票分你一半几乎一模一样，但是用这种方法做这个题会超时

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int a[100005];
int dp[500005];
int main()
{int n;while(~scanf("%d",&n)){mem(a,0);mem(dp,0);int sum=0;for(int i=0; i<n; i++){scanf("%d",&a[i]);sum+=a[i];}int v=sum/2;for(int i=0; i<n; i++)for(int j=v; j>=a[i]; j--)dp[j]=max(dp[j],dp[j-a[i]]+a[i]);printf("%d\n",sum-2*dp[v]);}return 0;
}

代码2（深搜DFS）：

//由于深搜还没有学，等学了以后补上自己的代码，现在先贴一个别人的

#include <stdio.h>
#define abs(x) (x) > 0 ? (x) : -(x)
int n, arr[22], sum, min, temp, t;void DFS(int pos)
{if((t = abs(sum - 2 * temp)) < min) min = t;if(pos == n) return;for(int i = pos; i < n; ++i){temp += arr[pos];DFS(i + 1);temp -= arr[pos];}
}int main()
{while(scanf("%d", &n) == 1){temp = sum = 0;min = 200002;for(int i = 0; i < n; ++i){scanf("%d", arr + i);sum += arr[i];}DFS(0);printf("%d\n", min);}return 0;
}

这篇关于NYOJ325 zb的生日(01背包，深搜DFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---