DFS(二)

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      //题目:从n个数中选k个数使得和为x，且平方和最大的一组
     
    
   

    

     

    
    

     

      //最大平方和为maxSumSqu
     
    
   

    

     

    
    

     

      int n,k,x,maxSumSqu=-1,A[9999];
     
    
   

    

     

    
    

     

      int nowK;
     
    
   

    

     

    
    

     

      //temp存放临时方案，ans存放平方和最大的方案
     
    
   

    

     

    
    

     

      vector<int> temp,ans;
     
    
   

    

     

    
    

     

      int sumSqu;
     
    
   

    

     

    
    

     

      //当前处理index号整数，当前已选整数个数为nowK
     
    
   

    

     

    
    

     

      //当前已选整数之和为sum，当前已选整数平方和为sumSqu
     
    
   

    

     

    
    

     

      void DFS(int index,int nowK,int sum,int maxSumSqu){
     
    
   

    

     

    
    

     
	if(nowK==k&&sum==x){//找到k个数的和为x
     
    
   

    

     

    
    

     
		if(sumSqu>maxSumSqu){
     
    
   

    

     

    
    

     

      			maxSumSqu=sumSqu;//更新最大平方和
     
    
   

    

     

    
    

     

      			ans=temp;//更新最优方案
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
	return;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//已经处理完n个数，或者超过k个数，后者和超过x，返回
     
    
   

    

     

    
    

     
	if(index==n||nowK>k||sum>x)  return;
     
    
   

    

     

    
    

     
	//选index号数
     
    
   

    

     

    
    

     

      	temp.push_back(A[index]);
     
    
   

    

     

    
    

     
	DFS(index+1,nowK+1,sum+A[index],sumSqu+A[index]*A[index]);
     
    
   

    

     

    
    

     

      	temp.pop_back();
     
    
   

    

     

    
    

     
	//不选index号数
     
    
   

    

     

    
    

     
	DFS(index+1,nowK,sum,sumSqu);
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/104020164