#前面我们已经把深度优先搜索给传授给了各位,接下来我们进行深搜搜索树的学习啦
加入有这样一道题:现在有n个数,我们从中选取k个数字,要求所选择k个数字之和为S。
我们这样思考,我们对于一个数字只有两种可能,选择或者不选择,如果从第一个数值开始分析,我们的选择和不选择,像不像一条路径?这样延伸下去不就是一颗树么?
那其实我们的思路大致也出来了,然后我们进行判断:
我们在递归中进行选或者不选的操作。
同时判断我们是否得到了最后的期望,达到了期望就结束我们的递归。
深搜搜索树:
我们首先需要定义一个数组,来存储我们n个数字。
1.我们在dfs中需要判断当k==K时,无论搜没搜到,都要结束(可行性剪枝1)
2.当k<K时,如果sum>=S,则无需再搜索(可行性剪枝2)
3.通用终止条件:当dep=n+1,我们就跳出循环。
我们的代码部分也很简洁:
#include<bits/stdc++.h>
using namespace std;
//深搜搜索树:
//n个数,从中选取k个数字,要求k个数字之和为s
int n,K,S;
int a[101];
bool flag=false;
//状态:k为当前已经选了k个数字,sum表示k个数字之和
void dfs(int k,int sum,int dep)
{
//可行性剪枝1:当k==K时,无论搜到没搜到,都要结束
if(k==K)
{
if(sum==S)
{
flag=true;
return;
}
}
//可行性剪枝2:当k<K时 ,sum>=S,无需再搜索
if(sum>=S)
return;
//通用终止条件
if(dep==n+1)return;
//在第dep层,选或不选第dep个数
dfs(k+1,sum+a[dep],dep+1);//选
if(flag==true) return;
dfs(k,sum,dep+1);//不选
}
int main()
{
cin>>n>>K>>S;
for(int i=1;i<=n;i++)cin>>a[i];//用scanf节约时间
dfs(0,0,1);
cout<<(flag?"yes\n":"no\n");
return 0;
}