【复习】回溯法

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*
回溯法思路：
1 确定解空间树的结构：排列树 or 子集树；m叉树（分两种），n层，mn分别对应题中哪些变量
2 确定限界函数：最优解或者限制变量（如最小价格，或者路线是否存在）
3 确定可行解，以及更新方式
4 确定最终输出，并在设计算法时更新答案（不能忽略）

注：解空间树的结构一般有三种：
	一种是子集树问题，比如01背包，每次的选择相对独立，互不影响。
	一种是排列树问题，如货郎问题，核心是perm算法。特点：不走重复路，不选重复人。
	一种是路径问题，比如迷宫，n后问题，每次有上下左右四步可走。
	有时可以用for循环代替对称选择问题，比如符号问题，换算成01for循环实现，可以简化过程。
	

易错点：
	1 迷宫不能走重复路，走完要标记
	2 迷宫不需要回溯，因为要走完才算
	3 先剪枝，再更新可行解，因为此时函数传入的值是上一次递归的值

*/


//1 最小重量机器设计问题 p157
/*
解空间树：子集树
m供应商：m叉树
n个零件：n层树
剪纸函数：价格上限c，最小重量minw
可行解：whight,prince;
*/
//注意答案：ans[i]=j,第i个零件从j供应商处买
#define n 7
#define c 5
int bestw,cp,cw;
int x[n + 1];
int p[n + 1][n + 1];
int w[n + 1][n + 1];
void traceback(int i) {
	if (i > n) {
		bestw = cw;
		for (int k = 1; k <= n; k++)
			printf("%d", x[k]);
	}
	for (int j = 1; j <= n; i++) {
		x[i] = j;
		cw += w[i][j];
		cp += p[i][j];
		if (cw < bestw && cp < c) {
			traceback(i + 1);
		}
		cw -= w[i][j];
		cp -= p[i][j];
	}
}

//2 排球运动员最优组合问题
/*
解空间树：排列树
n叉树（女），n层（男）
可行解：max(p[i][j]*q[j][i])
剪枝：最优解剪枝
时间复杂度：n！
输出：最大值
*/
#define n 10
int p[n + 1][n + 1], q[n + 1][n + 1];
int max, temp;
int r[n + 1];
void swap(int i, int j) {

}
void ball(int i) {
	if (i > n) {
		if (temp > max) {
			max = temp;
			for (int i = 1; i <= n; i++)
				printf("%d", r[i]);
		}
	}
	for (int j = i; j <= n; j++) {
		swap(r[i], r[j]);
		temp += p[j][r[j]] * q[r[j]][j];
		ball(i + 1);
		temp -= p[j][r[j]] * q[r[j]][j];
		swap(r[i], r[j]);
	}
}

//3 3n+1问题：偶数变为n/2，奇数变为3n+1，最终变成1，过程生成的序列长度最短的数字。
int _f3n1(int x,int sum) {
	if (x == 1)
		return sum;
	if (x >= 1) {
		if (x % 2 == 0) {
			_f3n1(x/2, ++sum);
		}
		else {
			_f3n1(x*3+1, ++sum);
		}
	}
}

//4 打枪得分问题（2020真题7）(递归、非回溯)
/*
每次射击有三种情况，1 射击得分 2 射击摧毁 3 打空枪，注意射击摧毁和打空枪是两种情况。
递归问题应先写出递归方程。
*/
//
int score = 0;
int max = 0;
int gun(int a[], int b[],int t,int j) {
	if (t > n) {
		if (score > max)
			max = score;
		return;
	}
	else {
		if (a[t] == b[j]) {
			score++;
			gun(a,b,t + 1,j+1);//射击得分
		}
			/*if (a[t + 1] == b[j+1])
				j++;*/
		gun(a, b, t+1, j);//放空枪
		gun(a, b, t + 1, j+1);//摧毁目标
		return;
	}
}

//5 m着色问题
#define m 3
#define n 5
int x[n + 1];//n+1编号节点的颜色
int g[n + 1][n + 1];
int sum;
bool iscolor(int i) {
	for (int j = 1; j < i; j++)
		if (g[i][j] * x[i] == x[j])
			return false;
	return true;
}
void traceback(int i) {//第i个结点
	if (i > n) {
		sum++;
		for (int j = 1; j <= n; j++)
			printf("%d", x[j]);

		return;
	}
	else {
		for (int k = 1; k <= m; k++) {//颜色序号
			x[i] = k;//第i个结点的颜色是k
			if (iscolor(i))
				traceback(i + 1);
			x[i] = 0;
		}
	}
}

//6 符号三角形
/*
解空间树：子集树
剪枝函数：若+或者-数量超过一半，则剪枝；结果判断剪枝
解：符号三角形数量n
关键：求+、-号数量;for循环实现
*/
/*
易错：过程值在回溯时要重新减去
*/
#define n 7
int count, sum = 0;//负号
int half = (1 + n) * n / 4;
int x[n + 1][n + 1];
void traceback(int t) {

	if ((count > half) || (t * (t - 1) / 2 - count > half))
		return;
	if (t > n)
		sum++;
	else {
		for (int i = 0; i <= 1; i++) {
			x[1][t] = i;
			count += i;

			for (int j = 2; j <= t; j++) {
				x[j][t - j + 1] = x[j - 1][t - j + 1] && x[j - 1][t - j + 2];
				count += x[j][t - j + 1];
			}

			traceback(t + 1);

			for (int j = 2; j <= t; j++)
				count -= x[j][t - j + 1];

			count -= i;
		}
	}
}

///7 旅行售货员问题
//两个判断最重要
int A[10][10];
int x[10];
int best, cc, bestx[10];
#define n 10;
void swap(int i, int j) {
}
void traveling(int i) {
	if (i == n) {
		if (A[x[i - 1]][x[i]] && A[x[i]][1] && cc + A[x[i - 1]][x[i]] + A[x[i]][1] <= best) {
			best = cc + A[x[i - 1]][x[i]] + A[x[i]][x[1]];
			for (int j = 1; j <= n; j++)
				bestx[j] = x[j];
		}

	}
	else {
		for (int j = i; j <= n; j++) {
			if (A[x[i - 1]][x[j]] && cc + A[x[i - 1]][x[j]] <= best) {
				swap(x[i], x[j]);
				cc += A[x[i - 1]][x[j]];
				traveling(i + 1);
				cc -= A[x[i - 1]][j];
				swap(x[i], x[j]);

			}
		}
	}
}

//9 n后问题
/*
解题步骤：
	1 判断该行是否有棋子，有进入下一行，重新判断，没有进入2
	2 标记改行不可以放的位置：方法是遍历之前所有的棋子，对斜率在该行上的映射进行标记不能放
	3 
*/
#define n 8
bool line[n + 1];
bool isplace;
int x[n + 1];
int count = 0;
void Generatep(int j) {/*j是列*/  //按列考虑
	if (j == n + 1) {
		count++;
		for (int k = 1; k <= n; k++) {
			printf("%d ", x[k]);//打印四个数字，分别显示哪几行
		}
		printf("\n");
		return;
	}


	for (int i = 1; i <= n; i++) {
		if (line[i]) { //第i行还没有皇后


			isplace = 1;
			for (int pre = 1; pre < j; pre++) {//遍历之前的皇后，判断该行能不能放
				if (abs(j - pre) == abs(i - x[pre])&&(x[j]==x[pre])) {//两个皇后的位置在同一个斜线或同一行（列已经排除了）上，参考王晓东p135，因为j是固定的，所以只要有一个i满足同斜率，这一行都不能放
					isplace = 0;
					break;
				}
			}


			if (isplace) {//皇后可以放在第i行，和之前的皇后都不重叠
				x[j] = i;// [i，j]
				line[i] = false;//i行不能放
				Generatep(j + 1);
				line[i] = true;
			}
		}
	}
}

//10 走迷宫问题
/*
注意：走迷宫以走出迷宫为结果，因此过程不需要回溯
需要回溯的类型有：走路消耗某个能量，走不同的路，消耗不一样，若还没到终点能量用完了，则需要回溯
*/
//解空间树：所有可行解，上下左右四步为叉树
//剪枝：迷宫边界和X
//可行解：a[i][j]
//答案：所有路径数量
//不能走重复路
#define x 5
#define y 5
int sum = 0;
char maze[x][y];
int _maze(int a, int b) {
	if (maze[a][b] == 'E') {
		sum++;
		return;
	}else{
		maze[a][b] = 1;
		if (maze[a][b] == 'X' || maze[a][b] == 1)
			return;
		if (a == -1 || a == x || b == -1 || b == y)//简化模型，无需在下面重复。
			return;
			_maze(a, b - 1);
			_maze( a,b + 1);	
			_maze(a - 1, b);	
			_maze( a + 1, b);		
	}
	return sum;
}

//11 象棋马A走到马B最少步数
//走迷宫类题，步数过多时，可以用数组表示穷举步伐情况，并通过for循环实现。
void horse(int num ) {
	for (int i = 0; i < num; i++) {
		int x1, y1, x2, y2;
		scanf_s("%d%d%d%d", &x1, &y1, &x2, &y2);
		int min = 999;
		int min=tracebackhores(x1, y1, x2, y2,min);
		printf("%d", min);
	}
}
int step=0;
int tracebackhores(int x1, int y1, int x2, int y2, int min) {
	int a[8][2] = { {2,1} ,{2,-1} ,{-2,1} ,{-2,-1} ,{1,2} ,{-1,2}, {1,-2} ,{-1,-2} };
	if (x1 == y1 && x2 == y2) {
		if (step < min)
			min = step;
		step = 0;
		return min;
	}
	else {
		
		for (int i = 0; i < 8; i++) {
			if (x1 < 0 || x1>26 || y1 < 0 || y1>10)
				return;
			step++;
			int temp=tracebackhores(x1+a[i][0], y1+a[i][1], x2, y2, min);
			if (temp >= min)
				return;
		}
		
		

	}
}

//12 3.7 摘花生
#define m 10 
#define n 10
int max=0,sum;
int p[m+1][n+1];
void peaunt() {
	int t,i,j;
	scanf("%d", t);
	for (int z = 0; z < t; z++) {


		sum = 0;
		for (i = 1; i <= m + 1; i++)
			for (j = 1; j <= n + 1; j++)
				if (i > m || j > n)
					p[i][j] = 0;
				else scanf("%d", p[i][j]);
		traceback(1, 1);

		printf("%d", sum);
	}

}
void traceback(int a,int b) {
	if (a == m && b == n) {
		if (sum > max)
			max = sum;
		return;
	}
	else {
		if (a > m || b > n)
			return;
		sum += p[a][b];
		traceback(a + 1, b);
		sum -= p[a + 1][b];
		traceback(a, b + 1);
		sum -= p[a][b + 1];
	}
}

//13 图的深度遍历，一笔画走完，并输出路径所构成的数，取最小的数值
/*
本题有一个隐藏结论，按照邻阶矩阵深度遍历，得到的第一个一笔画遍历的数值数组是最小的（以进制存储）
*/
int min(int a, int b) {
	if (a > b)
		return b;
	else return a;
}
int max2(int a, int b) {
	if (a > b)
		return a;
	else return b;
}
int ma = 999, mb = 0;
int ans[n],nn=0;
int edge[n][n];
void dfstravel() {
	for (int i = 0; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		edge[a][b] = 1;
		edge[b][a] = 1;
		ma = min(ma, min(a, b));
		mb = max2(mb, max2(a, b));
	}
	dfs(1);
	for (int i = nn - 1; i > 0; i--)
		printf("%d", ans[i]);
}

void dfs(int t) {
	for (int i = 0; i < n; i++) {
		if (edge[t][i] == 1) {
			edge[t][i]--;
			edge[i][t]--;
			dfs(i);
		}
	}
	nn++;
	ans[nn] = t;
}

//14 
void mouse(int t, int len) {
	if (nn == len) {
		nn--;
		ww = 0;
		rr = 0;
		return;
	}
	for (int i = 0; i < 2; i++) {
		nn++;

		if (t == 0)
			ww++;
		if (t == 1)
			rr++;
		if (ww == 0 || ww % 2 == 0)
			sum++;
		mouse(i, len);
	}
}
void mou(int t, int a, int b) {
	for (int i = a; i <= b; i++)
		mouse(0, i);

	printf("%d", sum);
}

//15 旅行航班最少费用问题
int k = 4;
int scr = 0, dst = 3;
int fee = 0,minfee=0;
int time = 0;
typedef struct graph {
	int edge[n][n];
};
void airtravel(graph g,int t) {
	if (t == dst) {
		if (fee < minfee)
			minfee = fee;
		return;
	}
	else {
		if (fee > minfee || time > k)
			return;
		for (int i = 0; i <= n; i++) {
			if (g.edge[t][i] != 0) {
				time++;
				fee += g.edge[t][i];
				airtravel(g, i + 1);
				time--;
				fee -= g.edge[t][i];
			}
			
		}
	}
}

int main() {
	int a = 1, b = 20,max=0, k;
	for (int i = a; i <= b; i++) {
		k=_f3n1(i,1);
		if (k > max)
			max = k;
	}
	printf("%d", max);
	system("pause");

	//m着色问题
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf_s("%d", &g[i][j]);

	traceback(1);
	printf("%d", sum);

	//旅行售货员
	int a, b, w;
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++) {
			scanf("%d%d%d", a, b, w);
			A[i][j] = w;
		}
	for (int i = 1; i <= n; i++) {
		x[i] = 0;
		bestx[i] = 0;
	}
	x[1] = 1;
	best = 999;
	cc = 0;
	traveling(2);
	printf("最优解为%d", best);
	for (int j = 1; j <= n; j++)
		printf("%d", bestx[j]);


	//n后问题
	for (int m = 0; m <= 8; m++) {
		line[m] = true;
	}

	Generatep(1);
	printf("%d\n", count);
	system("pause");
}

int sum,ww=0,rr=0,nn=0;