DFS之回溯算法的问题

回溯算法的基本问题主要分为：1.排列问题2.组合问题

很多其他的算法题都基于这两种基本问题而产生

回溯问题的基本模板

基本模板：1.出口

                  2.判断部分/条件部分/访问设置部分

                  3.递归回溯部分

洛谷p1706

根据题意我们可知，这是一个排列问题，涉及到高中的A排列问题

排列的基本模型结构

#include 
using namespace std;
int ans[100] = { 0 };
int len;
int n;
int visit[10] = { 0 };

 len表示输入的最大数字，ans数组用来储存排列顺序

visit数组表示是否访问过（将前面已经出现过的数字设为1，而没有出现过的设为0）

int main()
{
	ans[0] = 0;
	cin >> n;			//输入n
	len = n;
	for (int i = 1;i <= n;i++)
	{
		dfs(i, 1);
		visit[i] = 0;
	}
}

 dfs函数的定义设置为   void dfs（int i，int lenth）

i   表示要插入的数字          lenth表示要插入在数组的哪一个位置

在main函数中有一个循环，用来选择插入1-n中的数字

•  void dfs（int i，int lenth）
• {         
• if（出界   | |  lenth超过最大长度len  | |  这个数字访问过了  ）
•         return ；                                                //dfs的基本出口
• 这个数字我取过了
• 把数字插入到这个位置
• if（lenth== 最大长度）
• {         输出此时的排列顺序
•           return；
• }
• 递归加回溯
• }

void dfs(int z, int lenth)
{
	
	if (z > n || lenth > n||visit[z])
		return;
	ans[lenth] = z;
	if (lenth == len)
	{
		for (int i = 1;i <= len;i++)
			cout << "    " << ans[i];
		cout << 'n';
		return;
	}
	visit[z] = 1;

递归回溯部分

if（i没有访问过）

{        

        visit【i】=1；

        dfs（i，lenth+1）；                //递归插入

        visit【i】=0；                         //回溯

}

for (int i = 1;i <= n;i++)
	{
		if (!visit[i])
		{
			dfs(i, lenth + 1);
			
			
			visit[i] = 0;
		}
	}
	ans[lenth] = 0;
}

 题目要求：按照字典序输出

 基本思路：找到最小的组合情况并且按照字典序的大小顺序输出

• dfs（int n，int lenth）
• {
•     越界或者超出长度或者前面的数字==n
•               --》出口；
•     ans[lenth]=n；
•     判断饲料总和是否满足于最小维生素要求
•              判断是否满足最小长度（最少的饲料种类）
•                      满足的话替换，不满足-》出口
•    
• visit[i]=1；               //收录这个数字        
•  dfs（i+1，lenth）；       //平替
•  visit[I+1]=0;
•  ans[lenth]=i；     //回溯
• dfs（i+1，len）；//顺替
• }

#include 
using namespace std;

int v;									//维生素的种类
int g;									//饲料的种类
int V[260] = { 0 };						//需要的维生素量
int feed[160][260] = { 0 };				//饲料
int visit[160] = { 0 };							//访问数组
int c[26];							//c是寄存数据数组(最多有25种维生素)
int t = 1;
int ans[16] = { 0 };					//最后的答案数组,寄存的是下标
int minl = 1e9;
int b[16] = { 0 };

int main()
{	
	int i, j;
	cin >> v;
	for (i = 1;i <= v;i++)
		cin >> V[i];
	cin >> g;
	for (i = 1;i <= g;i++)
		for (j = 1;j <= v;j++)
			cin >> feed[i][j];
	dfs(1, 0);
	cout << minl+1 << " ";
	for (i = 0;i < minl + 1;i++)
		cout << ans[i] << " ";
	
}

bool Judge(int lenth)
{
	memset(c, 0, sizeof(c));
	for (int i = 0;i <= lenth;i++)
		for (int j = 1;j <= v;j++)
			c[j] += feed[b[i]][j];
	for (int i = 1;i <= v;i++)
		if (c[i] < V[i])
			return false;
	return true;
}
bool check()									//判断b是否比ans小
{
	int i = 0;
	int D_value=100;
	while (b[i] == ans[i]) { i++; }
	D_value = b[i] - ans[i];
	if (D_value > 0)	return  false;
	else return true;
}

void dfs(int i, int lenth)
{
	if (i > g || lenth > g||visit[i])			//越界return
		return;			
	b[lenth] = i;		
	if (lenth <= minl)
	{
		if (Judge(lenth))
		{
			if (lenth < minl) {
				minl = lenth;
				for (int i = 0;i <= lenth;i++)
					ans[i] = b[i];
				return;
			}
			if (lenth == minl)
				if (check())
				{
					for (int i = 0;i <= lenth;i++)
						ans[i] = b[i];
					return;
				}
		}
	}
	else return;
	visit[i] = 1;
	dfs(i + 1, lenth);
	b[lenth] = i;
	visit[i+1] = 0;
	dfs(i + 1, lenth + 1);

}