南阳理工 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)分别代表每个西瓜的重量 输出 输出分成两堆后的质量差 样例输入 5 5 8 13 27 14 样例输出 3

想法：

写下我的想法过程：刚开始我以为用动态规划就能解决，于是写了代码1，结果提交上去超时，想了会，没法改算法解决；就百度一下；

大吃一惊，配用搜索能节约大量时间；因为一般用动态规划用了两个for循环；时间复杂度大约为n*n；而配用搜索递归则能大大

缩减时间复杂度，于是写了代码2。

还是说下解题思路：首先我们想找出几个西瓜的总质量接近总西瓜质量的一半；于是想出了动态转移方程：

data[j]=max(data[j-a[i]]+a[i],data[j]);但是发现只用常规动态规划方法会超时的；于是；我们再回到原题，仔细想下：

其实对于每一个西瓜就两个选择，放入这组，不放人这组；在想求分成两堆后的质量差；不就是求（一组总质量m*2-西瓜总质量sum）的绝对值的最小值吗？

想到这就基本解决问题。

代码1

#include<stdio.h> int a[20]; int data[1000010]; int max(int x,int y) {     return x>y?x:y; } int main() {     int n;     while(scanf("%d",&n)!=EOF)     {     int i,j,t;     int sum=0,sum1;     for(i=1;i<=n;i++)     {         scanf("%d",&a[i]);         sum=sum+a[i];     }     sum1=sum/2;     /*for(i=1;i<=n-1;i++)     {         for(j=1;j<=n-i;j++)         {         if(a[j]>a[j+1])         {         t=a[j+1];a[j+1]=a[j];a[j]=t;         }         }     }*/     for(i=1;i<=n-1;i++)     {         for(j=sum1;j>=a[i];j--)         {         data[j]=max(data[j-a[i]]+a[i],data[j]);         }     }     printf("%d\n",sum-2*data[sum1]);     }     return 0; }

代码2：

这种想法真的值我们思考

#include<stdio.h> #include<math.h> int sum,maxx,n; int a[25]; void dfs(int s,int i)//s表示质量，i表示西瓜下标 {     if(i==n+1)         return ;     if(fabs(2*s-sum)<maxx)         maxx=fabs(2*s-sum);     dfs(s+a[i],i+1);//放入这组     dfs(s,i+1);//不放入这组 } int main() {     while(scanf("%d",&n)!=EOF)     {     int i;     sum=0;     maxx=9999999;     for(i=1;i<=n;i++)     {     scanf("%d",&a[i]);     sum=sum+a[i];     }     dfs(0,1);     printf("%d\n",maxx);     }     return 0; }