NYOJ 325 zb的生日

题目链接~~>

做题感悟：开始做这题时首先想到的是背包，认真优化了一下险过，后来看了学长的博客也可以用搜索过。

解题思路：其实一个深搜就搞定，只是剪枝不好剪枝。

代码：（搜索非本人）

      #include <stdio.h> 
      #define max(a,b) a>b?a:b 
      int avg,ans,n,w[21],sum[21];
      void dfs(int i=n,int cnt=0)//i为第i个西瓜 cnt为第i个西瓜以后的重量的各种组合 
      {
      if(i == 0)//二叉树往下找出所有的cnt，ans为最大的cnt 
       {
       ans = max(ans,cnt);//找出最大的结果（因为下面的代码保证了结果不会超过平均数，最大结果就是最优解） 
      return ;
       }
      if(ans == avg || cnt+sum[i] <= ans) //如果找到平均数或者cnt加上前面所有的西瓜重量都不超过这个最优解，
      return ; //那么就不用往下算了！ 
      if(cnt+w[i] <= avg)
       dfs(i-1,cnt+w[i]);//要第i个西瓜（如果要了第i个西瓜就超过了平均数，就不要了） 
       dfs(i-1,cnt); //不要第i个西瓜 
      }
      int main()
      {
      while(~scanf("%d",&n))
       {
       ans = 0;
      for(int i=1;i<=n;i++)//注意第一个西瓜存在w1里，而不是w0 
       {
      scanf("%d",&w[i]);
       sum[i] = sum[i-1] + w[i];//求出前n项和 
       }
       avg = sum[n]/2; //求出平均数 
       dfs(); //开始遍历，注意要求的是最大的不超过平均数的数 
      printf("%d\n",sum[n]-2*ans);
       }
      return 0;
      }
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/18074373