深度优先「dfs」

搜索主要是回溯法和分支限界法的使用

• 搜索算法是利用计算机的高性能有目的地穷举一个问题的部分或全部可能情况
• 搜索过程实际上是根据初始条件和扩展规则构造一棵==解答树==来搜索答案

举例 迷宫问题

• 按照某个条件往前搜索,
• 如果前进中遭到失败 (比如死胡同) 则退回另选通路搜索,
• 直到找到答案

这样的算法要用到递归. 如果要判断能否从某点到终点, 程序框架:

bool dfs(V){	// 参数可以不止一个
	if(V is aim) return true;		// 搜索的出口
	if(V have used) return false;
	mark V as used;
	while (every splits U){			// 搜索的循环条件
		if(dfs(U)) return true;
		return false;
	}
	
}

举例 背包

选数

解题思路: 对于每个数, 只有两种选择, 选与不选dfs(index+1,diji,sum); dfs(index+1,diji+1,sum+a[index]); 对应这两种情况. 如果搜出界了, 或者数量到了, 就是出口

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAXN=1e5+20;
int n,k;
int a[MAXN];
int flag[MAXN];
int ans;
 
int isprime(int num){
	
	if(num==2) return 1;
//	if(num==0 || num==1) return 0;
	
	bool is=1;
	for(int i=2;i<num;i++){
		if(num%i==0){
			is=0;
			break;
		}
	}
	return is;
 
//if(b==0 || b==1) return 0;
//if(b==2) return 1;
//if(b%2==0) return 0;
//for(int i=2;i<sqrt(b)+1;i++)
//{
//if(b%i==0) return 0;
//}
//return 1;
 
}
 
void dfs(int index,int diji,int sum){
//	if(diji==k && index<=n+1){
//		if(isprime(sum)) ans++;
//	}else if(diji>k || index>n+1){
//		;
//	}else{
//		dfs(index+1,diji,sum);	// buqu
//		dfs(index+1,diji+1,sum+a[index]);	// qu
//	}
 
	if(diji==k){
		if(isprime(sum)) ans++;
		return;
	}
	if(index>=n+1){
		return;
	}
	dfs(index+1,diji,sum);	// buqu
	dfs(index+1,diji+1,sum+a[index]);	// qu
}
 
int main(){
	
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	dfs(1,0,0);
	cout<<ans;
	return 0;
}