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