深搜+记忆化+回溯_回溯加记忆化搜索

        今天我又来讲搜索了，开始我觉得搜索难，可懂了以后其实简单得要命。来看例题：

        一.烤鸡(来自这以后题目都是在这找的)

        题目描述：

        Hanke他有 1010 种配料（芥末、孜然等），每种配料可以放 11 到 33 克，任意烤鸡的美味程度为所有配料质量之和。现在， Hanke 想要知道，如果给你一个美味程度 n ，请输出这 1010 种配料的所有搭配方案。

        输出格式:

        第一行，方案总数。

        第二行至结束，1010 个数，表示每种配料所放的质量，按字典序排列。

        如果没有符合要求的方法，就只要在第一行输出一个 00。

______________________________________________________________

        这就是一个极其典型的弱化版搜索，或许有人会用10重循环，但那不是正解！！

        先看代码：

#include<bits/stdc++.h>
using namespace std;
int n,f[11],ans;
int df(int r,int z){这个是记录数量
	if(r==9&&n-z<=3){//不要再递归了，能简单尽可能的简单点
		ans++;
		return 0;
	}
	if(n-z>3*(10-r)){//判断退出，否则会MLE
		return 0;
	}
	for(int i=1;i<=n-z-1&&i<=3;i++){//递归
		df(r+1,z+i);
	}
	return 0;
}
int dfs(int r,int z){
	if(r==9&&n-z<=3){
		for(int i=1;i<10;i++){
			printf("%d ",f[i]);//输出记录数字
		}
		printf("%d\n",n-z);
		return 0;
	}
	if(n-z>3*(10-r)){
		return 0;
	}
	for(int i=1;i<=n-z-1&&i<=3;i++){
		f[r+1]=i;//记录
		dfs(r+1,z+i);
	}
	return 0;
}
int main(){
	cin>>n;
	if(n>30){//特判
		cout<<0<<endl;
		return 0;
	}
	if(n<10){//判断
		cout<<0<<endl;
		return 0;
	}
	for(int i=1;i<=n-9&&i<=3;i++){//计算方案数
		df(1,i);
	}
	cout<<ans<<endl;
	for(int i=1;i<=n-9&&i<=3;i++){//输出具体方案
		f[1]=i;//记录
		dfs(1,i);
	}
	return 0;
}

        这还没有用到回溯法，但可以先打个基础；

        来看第二题：

        二.选数(回溯)

        题目自己看，不再多说：

#include<bits/stdc++.h>
using namespace std;
int n,m,s[22],ans,f[22];
int ss(int x){//这个是判断素数
	if(x%2==0&&x>2)//不要把2漏了
		return 0;
	for(int i=3;i<x;i+=2){//最简单的判断素数法
		if(x%i==0)
			return 0;
	}
	return 1;
}
int dfs(int k,int z,int x){
	if(k==m){
		if(ss(z))//如果是素数答案+1
			ans++;
		return 0;
	}
    for(int i=x+1;i<=n;i++){
    	f[i]=1;//回溯
    	dfs(k+1,z+s[i],i);//搜索
    	f[i]=0;
    }
	return 0;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    	cin>>s[i];
    for(int i=1;i<=n-m+1;i++){//同上
    	f[i]=1;
    	dfs(1,s[i],i);
    	f[i]=0;
    }
    cout<<ans<<endl;//输出
    return 0;
}

        是不是很简单？再来个搜索+记忆化+回溯:

        三.枚举排列

        代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,f[11],v[11];
int dfs(int x,int r){
	f[r]=x;//简单记忆化
	if(r==k){
		for(int i=1;i<k;i++){//简单输出
			printf("%d ",f[i]);
		}
		printf("%d\n",f[k]);
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(!v[i]){//简单回溯
		    v[i]=1;
			dfs(i,r+1);
			v[i]=0;
		}
	}
	return 0;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		v[i]=1;
		dfs(i,1);
		v[i]=0; 
	}
	return 0;
}

        说实话以上的题目数据太弱了，不过适合新手练习，在看代码前可以自己尝试一下，记得留下赞来给个支持！！！