深度优先搜索
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。用c++更好地实现
//C++深度优先搜索(递归树模拟)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#define MAX_N 1000
using namespace std;
int a;
int n,k;
//已经从前i项得到了和sum，然后对于i项之后的进行分支
bool dfs(int i,int sum)
{
//如果前n项都计算过了 ，则返回sum是否与k相等
if(i==n)
{
return sum==k;
}
//不加上a的情况的分支
if(dfs(i+1,sum))
{
return true;
}
//加上a的情况的分支
//if(dfs(i+1,sum+a))
if(dfs(i+1,sum+a))
{
return true;
}
//无论是否加上a都不能凑成k就返回false
return false;
}
void solve()
{
//if(dfs(1,0))
if(dfs(0,0))
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
int main(void)
{
cin>>n;
int i,temp;
//for(i=1;i<=n;i++)
for(i=0;i<n;i++)
{
cin>>temp;
a=temp;
}
cin>>k;
solve();
return 0;
}
页:
[1]