算法介绍

有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。
回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯;否则，进入该子树，继续按深度优先策略搜索。
image.png

N皇后问题

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n后问题等价于在n×n格的棋盘上放置n个皇后，任何2 个皇后不放在同一行或同一列或同一斜线上。
Description
N皇后的排列，每行一个不冲突；N<=13。
Input
一个数字N (6 <= N <= 13) 表示棋盘是N x N大小的。
Output
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
解的输出顺序为从上到下从左到右，小的优先输出
Sample Input
6

Sample Output
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

代码

include
#include
using namespace std;
int q[20]; // 每个皇后所在的列数
int solves = 0; //解法
void queen(int i, int n)
{
if(i == n+1){ // 所有行全部走完，成功找到一种解法
solves++;
if(solves <= 3){ // 只输出前三个解
for(int j=1; j<=n; j++){
if(j == n){ // 格式控制，保证输出每行结尾处没有空格
cout << q[j];
cout << endl;
}
else
cout << q[j] << “ “;
}
}
return ;
}
else
for(int col=1; col<=n; col++){ // 遍历第i行的每一列，找到可以放置皇后的位置
bool flag = true;
for(int j=1; j if(col==q[j] || i+col==j+q[j] || i-col==j-q[j]){ //同一列||对角线
flag = false;
break;
}
}
if(flag){
q[i] = col;
queen(i+1, n);
}
}
}
int main()
{
int n;
memset(q,20,sizeof(q));
cin >> n;
queen(1, n);
cout << solves << endl;
return 0;
}

符号三角形

符号三角形的 第1行有n个由“+”和”-“组成的符号 ，以后每行符号比上行少1个，2个同号下面是”+“，2个异 号下面是”-“ 。计算有多少个不同的符号三角形，使其所含”+“ 和”-“ 的个数相同 。 n=7时的1个符号三角形如下:
+ + - + - + +
+ - - - - +
- + + + -
- + + -
- + -
- -
+
Input
每行1个正整数n <=24,n=0退出.
Output
n和符号三角形的个数.
Sample Input
15
16
19
20
0
Sample Output
15 1896
16 5160
19 32757
20 59984
这道题应该用深搜去构造顶层，然后推算出其他的层，在推算的同时进行给其中一种符号的计数，最后判断该符号的数是不是总符号数的一半，剩下的一些细节(诸如符号总数是否可以整除2、如何在输入0时结束程序等)我就不解释了，不过代码里的注释中会有。

代码

include
using namespace std;
int n,total,sum;
int word[30][30]; //存储符号的数组
void wxy() //函数名没有含义
{
int x=n,y=0; //x用于枚举层数，y用于计算其它层负号个数
while(x—) //枚举层数
for(int i=1;i<=x;i++)
{
word[x][i]=(word[x+1][i]+word[x+1][i+1])%2; //定义第n-x+1层的第i个符号
if(word[x][i]) y++; //若word[x][i]为负号，其它层负号个数加1
}
if(sum+y==n(n+1)/2/2) total++; //若负号的个数为符号总数的一半，情况数加1(运用了等差数列)
}
void dfs(int x)
{
for(int i=0;i<2;i++) //0为正号，1为负号
{
if(i) sum++; //给题目中顶层的负号计数
word[n][x]=i; //定义顶层的第x个符号是正还是负
if(x==n) wxy(); //若顶层的所有符号定义完毕，计算其它层的负号个数
else dfs(x+1); //定义顶层的第x+1个符号
if(i) sum—; //回溯
}
}
main()
{
while(cin>>n&&n) //输入n，判断n为不为0
{
cout< if((n(n+1)/2)%2) {cout<<”0”< dfs(1);
cout< total=sum=0;
}
https://blog.csdn.net/weixin_43272781/article/details/83046268

迷宫问题

题目描述

一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。

【输入】

第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 ≤ n ≤ 100)，表示迷宫的规模是n n的。接下来是一个n n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。

【输出】

k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。
【输入样例】
2
3
.##
..#
#..
0 0 2 2
5
…..
###.#
..#..
###..
…#.
0 0 4 0
【输出样例】
YES
NO

程序

include
using namespace std;
int ha,la,hb,lb;
int n;
int vis[110][110];
int u[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int flag;
void search(int x,int y){
if(x==hb && y==lb){
flag=1;
cout<<”YES”;
return;
}
for(int i=0;i<=3;i++){
int xx=x+u[i][0];
int yy=y+u[i][1];
if(xx>=0&&xx=0 && yy vis[xx][yy]=1; //标记为1,表示这个点用过了
search(xx,yy);
}
}
}
int main()
{
int time;
char t;
cin>>time;
int i;
for(i=1;i<=time;i++){
flag=0;
cin>>n;
memset(vis,0,sizeof(vis));// 重新初始化为0
for(int x=0;x for(int y=0;y cin>>t;
if(t==’#’)
vis[x][y]=1;
}
}
cin>>ha>>la>>hb>>lb;
search(ha,la);
if(flag==0) cout<<”NO”;
}
return 0;
}

简析

标准的二维数组移动类问题，可参考

判断条件也比较简单，从这个点出发，搜索所有能走到的点，如果当前搜索的点到达了目标点，flag标记为true，返回即可。若所有能到达的点都搜索完了，flag仍为false，则无法到达。

图的m着色问题

问题描述

给定无向连通图G和m种不同的颜色。
用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。
若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。
求一个图的色数m的问题称为图的m可着色优化问题。
输入
第1行有3个正整数n，k 和m，表示给定的图G有n个顶点和k条边，m种颜色。顶点编号为1，2，…，n。接下来的k行中，每行有2个正整数u,v，表示图G 的一条边(u,v)。
5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

输出

程序运行结束时，将计算出的不同的着色方案数输出。
48

代码

include
using namespace std;
#include
#include
int n; //图一共有n个顶点
int m; //m种颜色被选择
int k; //图中有k条边
int sum=0; //图的m着色种类
int x[101]; //存放当前的着色序列{…}
int a[101][101]; //图的邻接矩阵
//判断给点t着色为x[t]是否可行
bool OK(int t)
{
//可行的条件是当前点相邻的点不能与之同色
for(int i=1;i if(a[i][t]==1&&x[i]==x[t])
return false;
//如果所有与之相邻的点都不与之同色
return true;
}
void getsum(int i)
{
if(i>n){ //i>n说明找到了一个可行的涂色方案
sum++; //涂色方案数++
//这里可以选择性的输出解向量
return ;
}
//还没有到叶子节点，需要给当前节点可行的涂色
else{
for(int k=1;k<=m;k++){ //子树是一个m叉树
x[i]=k; //给第i个顶点着第k种颜色
if(OK(i))
getsum(i+1);
x[i]=0; //如果给第i个顶点着第k种颜色不可行
//不涂色，便于后续涂色
}
}
return ; //如果当前节点所有颜色都不可行，结束对子树的遍历，返回
}
int main()
{
cin>>n>>k>>m; //输入定点数，边数，着色种类数
int x,y;
memset(a,0,sizeof(a)); //给邻接矩阵赋初值
for(int i=1;i<=k;i++){
cin>>x>>y;
a[x][y]=a[y][x]=1; //生成邻接矩阵
}
getsum(1);
cout< return 0;
}
https://blog.csdn.net/practical_sharp/article/details/102810568

01背包问题

假设N=3（有三件物品），三个物品的重量为{20，15，10}，三个物品的价值为{20，30，25}，对于一个最大承重为25的背包，求包中物品的组合最大的价值是多少？
题目的参考思路图如下，建议图文对照：
image.png
对三件物品分别进行编号1，2，3，初始情况背包是空的
1.首先我们把1号物品放进背包里，此时背包里只有一件物品，总重量为0+20=20，没有超过承重25，因此可以将1号物品成功放入背包内；
2.接下来尝试把2号物品放入背包内，但是发现包中1号物品和2号物品的重量和为20+15=35，超过了承重25，因此不能把2号物品放入背包内；
3.接着考虑3号物品，此时包中只有1号物品。发现1号物品和3号物品的重量和为20+10=30，超过了承重25，因此3号物品也不能放入背包内；
4.由于只有3件物品，并且对于每一种物品我们都考虑过是否将其放入背包内，也就是找到了一种基本情况。找到一个基本情况后，我们就可以看看包里的物品的总价值了。这里包里只有一个1号物品，因此总价值为20；
5.重点来了！回溯过程：每次找出一种满足条件的基本情况就进行一次回溯，找到最后放入包中的物品并将其取出，接着考虑是否放入编号在这个物品之后的第一个物品。这里我们就把1号物品取出，接下来考虑是否放入2号物品；
6.取出1号物品后背包是空的，此时如果放入2号物品，背包总重量为15，没有超过背包承重，因此把2号物品放入背包内；
7.类似地，考虑将3号物品放入背包内。由于2号物品和3号物品的重量和为15+10=25，没有超过承重25，因此将其放入背包内；
8.由于考虑完了3号物品，因此又找到了一个基本情况，记下此时包里物品的总价值，为30+25=55。由于55高于上一种基本情况的总价值，因此将最优解更新为55；
9.进行一次回溯，取出背包中最后放入的物品，也就是3号物品，但是注意：当最后放入背包中的物品恰好是编号最大的物品时，需要额外进行一次回溯。为什么呢？因为编号最大的物品之后已经没有编号更大的物品了，因此没有可以考虑的下一种情况，只能在上一个层面上在进行一次回溯才能产生可能的最优解。（此处不必考虑只放入2号物品的情况，因为一定不是最优解，原因可以自己思考一下） 这里再回溯一次，也就是将倒数第二个放入包中的物品取出来，这里就取出2号物品。先后取出3号物品和2号物品之后包应该处于空的状态。
10.上一步中取出了2号物品，因此这一步直接考虑能否放入3号物品，简单的判断后即可得出可以放入，并且同上理也可以得出这是一种基本情况，但是由于包中只有3号物品，总价值为25，没有超过当前的最优解55，因此将该情况忽略。
11.最后一次回溯，取出包中的3号元素。由于此时包已经空了，并且最后一次取出的是编号最大的元素，那么说明算法已经完成了所有情况的遍历，算法终止，55是最优解。

程序代码

include
#include//由于问题中的包是需要进行后进先出的操作，因此考虑到使用栈这种数据结构（后进先出）
using namespace std;
int maxValue(int w[], int v[], const unsigned& length, const unsigned& capacity)
{
stack Bag;//首先构造出一个空的背包
int max = 0;//不同装入情况中背包中物品最大的价值
int weight = 0;//当前背包中物品的总重量
int value = 0;//当前背包中物品的总价值
int i;
for (i = 0; ; i++)
{
if (weight + w[i] <= capacity)//第一种情况：背包装入该物品后不会超重
{
Bag.push(i);//将该物品装入背包中
weight += w[i];//装入物品后背包重量增加
value += v[i];//装入物品后背包中物品的价值增加
}
else//第二种情况：装入该物品后背包超重，则不能将该物品装入包中，相当于什么也不做
{
//此处用else语句只是方便理解这是另外一种情况，可以省略
}
//当从第一个物品考虑到了最后一个物品时，就确定了一个可以满足条件的装包方法（一个方法就是确定了一个规定每一个物品是否装进包里的策略）
if (i == length - 1)
{
//接下来将本次装包物品价值与当前最高的装包物品价值进行比较，保留较大的一个
if (max < value)
{
max = value;
}
//此时取出最后装进包里的一件物品并对其下一件物品进行考虑（这就是算法的重点：回溯的过程！）
{
i = Bag.top();//取出上一件装入的东西（这就是回溯的过程）
Bag.pop();
weight -= w[i];//取出东西后背包重量减轻
value -= v[i];//取出物品后背包总价值也会降低
if (i == length - 1)//特殊情况：如果最后装进包里的物品本来在就是编号最大的物品，那么它后面就没有其他物品了，循环必定终止
{
if (Bag.empty())break;//当所有物品都被从包中拿出来后，这是说明已经遍历完所有情况，查找结束（相当于解空间树中最右边的子树已经走完了）
i = Bag.top();//取出上一件装入的东西（这就是回溯的过程）
Bag.pop();
weight -= w[i];//取出东西后背包重量减轻
value -= v[i];//取出物品后背包总价值也会降低
}
}
}
}
return max;
}

int main(void)
{
unsigned num, capacity;
cout << “请输入物品的个数：”;
cin >> num;
int weights = new int[num];
int values = new int[num];
cout << “请输入每件物品的重量：”;
for (unsigned i = 0; i < num; i++)
{
cin>>weights[i];
}
cout << “请输入每件物品的价值：”;
for (unsigned i = 0; i < num; i++)
{
cin >> values[i];
}
cout << “请输入包的最大承重：”;
cin >> capacity;
cout << “该问题的最优解为：” << maxValue(weights, values, num, capacity);
return 0;
}
https://blog.csdn.net/hanmo22357/article/details/124371395?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165551833716782388071150%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=165551833716782388071150&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-14-124371395-null-null.142^v17^control,157^v15^new_3&utm_term=01%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E5%9B%9E%E6%BA%AF%E6%B3%95c%E8%AF%AD%E8%A8%80&spm=1018.2226.3001.4187