书写结构：解空间和解结构，剪枝策略，示例，代码，时间复杂度分析

5-1子集和问题

image-20230102174153224

1. 解空间和解结构

类似于0-1背包问题，对于S大小为n的子集和问题，解空间是由长度为n的0-1向量组成，解的结构为子集树，如对于上述示例的解，解空间即为(1,1,1,0,0,0)

2. 剪枝策略

注意到题目说S是正整数的集合，c是正整数，故深搜的过程一定使得子集和增加或不变。

考虑在某节点处向下搜索的过程，设当前层数为k（即当前考虑是否加入数S[k]到子集中）

约束函数：维护变量cw表示当前子集和，若cw+S[k]>c，则剪去左子树

限界函数：计算变量rw表示剩余的整数之和(S[k+1:n-1]之和)，若cw+rw<c，即将之后所有整数加入子集也无法得到解，故减去右子树

对于本题而言，如果只要一个可行解的话，可以在搜索每个节点的时候，在考虑完是否加入数S[k]之后，判断S[k]是否等于c，若等于，则无需再搜索了

3. 示例

太多了不太好画，减少点数据量：

1
2
3 10
2 2 6

image-20230102221034796

4. 代码

这里就没弄文件读写了（可以直接粘贴下面的输入测试啦）

输入1：

1
2
5 10
2 2 6 5 4

输入2：

1
2
5 10
2 11 12 5 4

得到一个解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <windows.h>
using namespace std;
const int N=100010;
int S[N],res[N];
int n,c;
int num=0;//解的数量
void dispsolution(int res[])
{
    cout<<"第"<<num++<<"个解"<<endl;
    for(int i=1;i<=n;i++)
    {
     if(res[i]) cout<<S[i]<<" ";
    }
    cout<<endl;
}
void dfs(int cw,int rw,int res[],int level)
{
    if(level>n)//到达叶节点了
    {
        if(cw==c)//找到可行解
        {
            for(int i=1;i<=n;i++)
            {
             if(res[i]) cout<<S[i]<<" ";
            }
            exit(0);//直接结束程序(会不会有点暴力)
        }
    }else{
        if(cw+S[level]<=c)//考虑是否进入左子树
        {
            res[level]=1;
            dfs(cw+S[level],rw-S[level],res,level+1);
        }
        rw=rw-S[level];//计算剩余整数之和(剩余整数不包括当前整数)
        //这里和博客不太一样(他rw算的是包括当前的整数的)
        if(cw+rw>=c)//考虑是否进入右子树
        {
            res[level]=0;
            dfs(cw,rw,res,level+1);
        }
    }
}
int main()
{
    cin>>n>>c;
    int rw=0;//为了方便计算rw,首先计算所有整数的和
    for(int i=1;i<=n;i++)//为了方便,从下标1开始
    {
        cin>>S[i];
        rw=rw+S[i];
    }
    dfs(0,rw,res,1);//cw=1,res存储解,从第一层开始
    if(num==0) cout<<"No Solution!"<<endl;
    return 0;
}

image-20230102214448956

image-20230102214508262

得到所有解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>

using namespace std;
const int N=100010;
int S[N],res[N];
int n,c;
int num=0;//解的数量
void dispsolution(int res[])
{
    cout<<"第"<<num++<<"个解"<<endl;
    for(int i=1;i<=n;i++)
    {
     if(res[i]) cout<<S[i]<<" ";
    }
    cout<<endl;
}
void dfs(int cw,int rw,int res[],int level)
{
    if(level>n)//到达叶节点了
    {
        if(cw==c)  dispsolution(res);//找到可行解
    }else{
        if(cw+S[level]<=c)//考虑是否进入左子树
        {
            res[level]=1;
            dfs(cw+S[level],rw-S[level],res,level+1);
        }
        rw=rw-S[level];//计算剩余整数之和(剩余整数不包括当前整数)
        //这里和博客不太一样(他rw算的是包括当前的整数的)
        if(cw+rw>=c)//考虑是否进入右子树
        {
            res[level]=0;
            dfs(cw,rw,res,level+1);
        }
    }
}
int main()
{
    cin>>n>>c;
    int rw=0;//为了方便计算rw,首先计算所有整数的和
    for(int i=1;i<=n;i++)//为了方便,从下标1开始
    {
        cin>>S[i];
        rw=rw+S[i];
    }
    dfs(0,rw,res,1);//cw=1,res存储解,从第一层开始
    if(num==0) cout<<"No Solution!"<<endl;
    return 0;
}

image-20230102214546946

image-20230102214609533

5. 时间复杂度分析

考虑最坏情况下时间复杂度，每个节点都进行搜索，处理每个节点所需的时间均为$O(1)$，一共有1+2+4+8+…+2^n^

=$O(2^{n+1})$个节点，故时间复杂度为$O(2^{n+1})$

参考：https://blog.csdn.net/gl620321/article/details/108801724

5-2 最小长度电路板排列问题

image-20230102223036593

image-20230102223107634

1. 解空间和解结构

类似于旅行商问题，对于n个电路板的最小电路板排列问题，其解空间为n个数的全排列，解结构为排列树

2. 剪枝策略

维护变量bestd表示当前的最小长度，假设此时选择第i个位置上的电路板，考虑选择第j个电路板(j>=i，因为i前面的已经选择好了)作为该位置上的排列，此时利用已经选择好的第1~第i个位置上的电路板（第i个位置刚刚选择好的）来计算连接块的最大长度，若该长度小于当前最优解，则继续进行下面位置的选择，否则第i个位置上不能选择第j个电路板，剪去该子树

3. 示例

示例数据量太大，减少点

1
2
3
4
5
4 4
1 1 1 1
1 1 0 1
0 0 0 1
0 1 1 0

4个电路板，L1={1,2},L2={1,2,4},L3={1,4},L4={1,2,3}

类似于下面的画法（排列树太多了，只画了一个子树）：

image-20230103104730475

最后的结果：

image-20230103102814230

4. 代码

输入文件 input.txt:

1
2
3
4
5
6
7
8
9
8 5
1 1 1 1 1
0 1 0 1 0
0 1 1 1 0
1 0 1 1 0
1 0 1 0 0
1 1 0 1 0
0 0 0 0 1
0 1 0 0 1

输入含义

L1={1,4,5,6},L2={1,2,3,6,8},L3={1,3,4,5},L4={1,2,3,4,6},L5={1,7,8}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include<fstream>
#include <vector>
using namespace std;

int n, m;
int bestx[10];// 这是最终的最优解排列顺序
int B[10][10];//电路板在连接块中的排列，是一个二维数组
int x[10], low[10], high[10];// 分别是当前的排列、最左边电路板、最右边电路板
int bestd=0;// 最优解

int len(int ii) {// 计算当前ii排列最小长度
	for (int i = 1; i <= m; i++) {
		high[i] = 0;
		low[i] = n + 1;// 先初始化最左边和最右边的值，
	}
	for (int i = 1; i <= ii; i++)// 对于第i行
		for (int k = 1; k <= m; k++)// k列
			if (B[x[i]][k] > 0) {// 如果第i个电路板在第k个连接块中，
				if (i < low[k])//low[k]代表第K个连接块的最左边的值，如果i比它小，则更新左值
					low[k] = i;
				if (i > high[k])
					high[k] = i;//如果比初始的右值大，则更新右值
			}
	int tmp = 0;
	for (int k = 1; k <= m; k++)
		if (low[k] <= n && high[k] > 0 && tmp < high[k] - low[k])
            //若连接块的长度无法得到（前面两个bool表达式不满足，不计算该连接块的长度）
			tmp = high[k] - low[k];//计算每个连接块的举例
	return tmp;
}
void swap(int* x, int i, int j) {// 交换i和j位置的值
	int tmp;
	tmp = x[i];
	x[i] = x[j];
	x[j] = tmp;
}
void backtrack(int i) {
	if (i == n) {// 如果到达末尾
		int tmp = len(i);// 计算当前排列最小长度
		if (tmp < bestd) {
			bestd = tmp;
			for (int j = 1; j <= n; j++)
				bestx[j] = x[j];
		} // 如果比最优解还要好，则更新bestx[]排列；
	} else {// 若不是末尾；
		for (int j = i; j <= n; j++) {
			swap(x, i, j);
			int ld = len(i);
			if (ld < bestd)
				backtrack(i + 1);// 则继续进入下一个数，
			swap(x, i, j);
		}
	}
}

int arrangeBoards() {
	bestd = n + 1;// 先假设一个很大的值
	for (int i = 1; i <= n; i++)
		x[i] = i;// 这里是最开始的排序；
	backtrack(1);
	return bestd;
}

int main(void) {
	ifstream ifs("input.txt");//文件输入流
	ifs>>n;
	ifs>>m;

	vector<int> temp(m);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ifs>>B[i][j] ;// 输入的电路板的二维数组排列
		}
	}
	int minLen = arrangeBoards();
	cout<<minLen<<endl;
	for (int i = 1; i <= n; i++)
		cout<<bestx[i]<<" ";
	ifs.close();
	return 0;
}

image-20230103102521881

5. 时间复杂度分析

对于最坏情况，每个节点都需要计算一次len，即序号运行len函数，而第i层节点运行len函数时间复杂度为$O(im)$，故最坏情况下所需时间为$T=O(m)(n-1)+O(2m)(n-1)(n-2)+…+O(nm)(n-1)!$，故最坏情况下时间复杂度为$O(mn!)$

5-3 最小重量机器设计问题

image-20230103110515293

题目两个要求，总价格不超过d，并且部件重量之和要最小

1. 解空间和解结构

对于n个部件，m个供应商的最小重量机器设计问题，其解空间为长度为n的向量，向量的每一项为1~m的整数，对应的解结构为排列树（也不是那种TSP的排列树，不过也是排列啦，姑且称之为排列树）

2. 剪枝策略

考虑第i个部件供应商的选择

约束函数：维护变量cp表示当前已经购得的部件的价格之和，假设考虑选择第j个供应商，若cp+c[i][j]>d，则剪去以该节点为根节点的子树，无需再进行搜索

限界函数：维护变量cw表示当前已经购得的部件的重量之和，变量bestw表示当前最优解的重量之和，假设考虑选择第j个供应商，若cw+w[i][j]>=bestw，则剪去该节点为根节点的子树，无需进行搜索

3. 示例

对于题中示例画树：

image-20230103210648180

4. 代码

输入：

1
2
3
4
5
6
7
3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2

没实现文件读写了~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
int n,m,d;//n个部件，m个供应商，总价格不超过d
int c[999][999];//c[i][j]为从供应商j购买部件i所花费的价格；
int w[999][999];//w[i][j]为......重量
int cw=0,cp=0;//当前部件的重量 价格
int bestw=999,bestp=999;//最优方案的重量，价格
int x[999];//当前部件i从供应商j购买
int bestx[999];//最优方案部件i从哪个供应商买


void backtrack(int i){
	if(i>=n){//到达最后一层 
		if(cp<=d&&cw<bestw){//如果价格没超过d，并且重量小于之前方案的bestw 
			bestw=cw;//重量更新 
			bestp=cp;//价格更新
			for(int k=0;k<n;k++){
				bestx[k]=x[k];//部件的供应商进行更新 
			}
		}
	}
	else{
	//所有的方式都尝试了一遍，比较找到最优的重量
		for(int j=0;j<m;j++){
			x[i]=j;//当前部件i的供应商为j
			cw=cw+w[i][j];
			cp=cp+c[i][j];
			if(cw<bestw&&cp<=d)//如果这次的选择要比之前方案的更优 
			backtrack(i+1); 
		//回溯
			cw-=w[i][j];
			cp-=c[i][j]; 
		}
	}
}
int main(){
	cin>>n>>m>>d;//n个部件，m个供应商，总价格不超过d
	int i=0,j=0;
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			cin>>c[i][j];//c[i][j]为从供应商j购买部件i所花费的价格；
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			cin>>w[i][j];//w[i][j]为......重量
		}
	}
	backtrack(0);//第i个部件
	cout<<bestw<<endl;//最优方案的重量
	for(int k=0;k<n;k++)
	cout<<bestx[k]+1<<" "; //因为j从0开始，所以输出的时候加一个1；

}

image-20230103200657123

5. 时间复杂度分析

考虑最坏情况，对于每个非叶子节点，搜索所需时间为$O(m)$，对于每个叶子节点，搜索所需的时间为$O(1)$，故最坏情况下所需时间为$T=m*(m+m^2+…+m^{n-1})+m^n=O(m^n)$

5-4 运动员最佳配对问题

image-20230103211224034

输入：

1
2
3
4
5
6
7
3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1

输出：

1
52

1. 解空间和解结构

将问题转换为男运动员选女运动员的问题，故n个男、女运动员的运动员最佳匹配问题的解空间为n个数的全排列，对应的解结构为排列树

2. 剪枝策略

考虑对第i个男运动员匹配女运动员的情况，其中变量Max存储当前最优解的竞赛优势，变量sum存储第1~i-1个已经匹配完成的男运动员的竞赛优势，计算第i~n个男运动员的最大可能的竞赛优势ctn，若cnt+sum<Max，则剪去该节点及其子树

其中第j个男运动员的最大可能的竞赛优势为该男运动员与所有女运动员进行匹配所得竞赛优势中最大者，存储到maxsum数组中

3.示例

image-20230103214009258

4.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

int n;
int boy[21][21],girl[21][21];   //分别用于存放男、女运动员的竞赛优势
int Max=INT_MIN;   //Max代表男女双方竞赛优势的总和的最大值
int sum=0;   //sum为临时求和
int data[21][21];   //data[i][]用于存放男运动员 i 配对后的双方竞赛优势
int maxSum[21];   //记录每个男生匹配后可达到的最大双方竞赛优势
int book[21];   //用于标记女运动员是否已匹配：book[0]未匹配；book[1]匹配

void dfs(int t)
{
    if(t>=n)   //t到达n之后，代表全部标记访问了,得到了最大值
    {
        Max=max(Max,sum);
        return ;
    }
    int ctn=0;   
//剪枝函数:之前t个已匹配好的男女运动员的sum与之后的 t->n-1 个男匹配女的最大值加起来与已经得到的Max比较，若前者<=Max，剪枝
    for(int i=t;i<n;i++)   //求t及t之后男生匹配女生的最大值的和
        ctn+=maxSum[i];
//若从第t组->第n组，当前搜索sum加上假设匹配后的最大值cxn，仍然小于Max ，就需要剪枝了，则Max为已经求得的最大值
    if(sum+ctn<Max)   
        return ;
    for(int i=0;i<n;i++)   //若cxn>=Max，要探索子树。从第t个男生开始匹配，找未匹配的女生
    {
        if(!book[i])   //第 i 个女生未匹配
        {
            book[i]=1;   //第 t 个男生匹配女生i
            sum+=data[t][i];   //加上男生t与女生i的男女双方竞赛优势
            dfs(t+1);   //为第i+1个男生匹配
            book[i]=0;   //若第 t 个男生匹配女生i得到的sum不大于Max，则回溯
            sum-=data[t][i];
        }
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)   //输入男运动员的竞赛优势
    {
        for(int j=0;j<n;j++)
            cin>>boy[i][j];
    }
    for(int i=0;i<n;i++)   //输入女运动员的竞赛优势
    {
        for(int j=0;j<n;j++)
            cin>>girl[i][j];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
        //对每个男生都求男女双方竞赛优势，则能得到i*j种结果（涵盖了P[i][j]*Q[j][i]与Q[i][j]*P[j][i]）
            data[i][j]=boy[i][j]*girl[j][i];   
            maxSum[i]=max(maxSum[i],data[i][j]);   //记录每个男生匹配后可达到的最大双方竞赛优势，用于后面的剪枝
        }
    }
    dfs(0);
    cout<<Max<<endl;
    return 0;
}

image-20230104104042126

5.时间复杂度分析

考虑最坏情况，每个节点都需要搜索，对于非叶子节点，其需要时间为$O(n)$，对于叶子节点，其所需时间为$O(1)$，故所需时间为$T=n(n+n(n-1)+…+n!)+n!=O(n*n!)$

5-5 无分隔符字典问题

image-20230103214343137

1. 解空间和解结构

由S为$L_k$子集可知n个符号，长度为k的无分隔符字典问题的解空间为长度为$n^k$的向量，其中向量每一项为0或1，表示$L_k$中某一项是否在S中，解结构为子集树

2. 剪枝策略

首先将$L_k$中所有字字符串放入数组L中，考虑是否放入下标为i的字符串：

约束函数：若该字符串与当前S集合中的任意字符串按照题目所给方式进行拼接，结果均不在S集合中，且不为该字符串本身，则考虑将其放入，搜索其左子树，否则剪去该节点的左子树

限界函数：考虑不放入该字符串，若将i+1~$n^k$的字符串均放入，若n^k^-i+S.size<best，则无需搜索其右子树，剪去该节点的右子树

3. 示例

假设$\sum=(a,b),L_k=\{aa,ab,ba,bb\}$,则$L_k$的一个最大无分隔符字典为$\{aa,bb\}$

image-20230104102358652

4. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
using namespace std;

int *ak;
int lk;
int n, k;
int best = 0; //最大无分隔符字典元素个数

vector<int> L;  //将所有的长度为k的数字字符串存到集合L中
set<int> S;  //当前字典中的字符串存储在集合s中


//将下标为L[]中下标为i的字符串存入集合s
void insert(int i)
{
    S.insert(L[i]);
}

//将下标为L[]中下标为i的字符串存入集合s
void erase(int i)
{
    S.erase(L[i]);
}

//将ak[]中起点为i，长度为k数字串转换为十进制数字
int digi(int i)
{
    int x = 0;
    for(int j=0; j<k; j++)
    {
        x *= 10;
        x += ak[j];
    }
    return x;
}

//判断字符串a和第b个字符串是否互不为前缀
bool pref(int a, int b)
{
    int bb =b;//这里用bb只是因为原代码不太对,我直接改了
    int x = a;
    int y = bb/10;//去掉最后一位，得到高k-1位(因为验证的时候这位是肯定要剔除的
    //按理说x也要剔除最高位，但是后面的循环不会碰到最高位，所以这里没剔除了
    for(int i=0; i<k-1; i++) //ak[0, k-2]存放x的低k-1位，ak[k-1, k-1 + (k-2)]存放y
    {
        ak[k-i-2] = x % 10;
        x /= 10;
        ak[2*k-i-3] = y % 10;
        y /= 10;
    }
    for(int i=0; i<k-1; i++) //相当于依次判断a2a3..akb1, a3a4..b1b2, akb1..bk-1是否已存在于S中，本程序中下标从0开始
        if(S.count(digi(i)) > 0||digi(i)==bb)  //如果已存在于S中
            return true;

    x = bb;
    y = a/10;
    for(int i=0; i<k-1; i++)//先放b再放a
    {
        ak[k-i-2] = x % 10;
        x /= 10;
        ak[2*k-i-3] = y % 10;
        y /= 10;
    }
    for(int i=0; i<k-1; i++)
        if(S.count(digi(i)) > 0||digi(i)==bb)
            return true;

    return false;
}

//判断当前下标为b的字符串是否可以加入字典
//将字符串a1a2..ak看作k位十进制数
bool oka(int b)
{
    int bb = L[b];
    set<int>::iterator it;  //定义迭代器
    it = S.begin();
    while(it != S.end())
    {
        int a = *it;
        if(pref(a, bb)) //如果a,b其中一个是另一个的前缀
            return false;
        it++;
    }
    return true;
}

//得到总元素个数为n，长度为m的全排列
void Perm(int list[], int dep, int m, int n)
{
    if(dep>m)
    {
        int x = 0;
        for(int i=1; i<=m; i++)
            x = x*10 + list[i];   //转换为十进制数字
        L.push_back(x);  //将所有的数字字符串存到集合L中

    }
    else
        for(int j=1;j<=n;j++)
        {
            swap(list[dep], list[j]);
            Perm(list, dep+1, m,  n);
            swap(list[dep], list[j]);
        }
}


void backtrack(int dep)
{
    if(dep >= lk)
    {
        if(S.size() > best)
            best = S.size();
        return;
    }
    if(oka(dep))
    {
        insert(dep);
        backtrack(dep+1);
        erase(dep);
    }
    if(lk-dep+S.size()>best)
    backtrack(dep+1);
}


int main()
{
    ifstream fin("input.txt");
    cout << "输入正整数n：";
    fin >> n; cout << n;
    cout << "\n输入正整数k：";
    fin >> k; cout << k;
    ak = new int[2*k];
    lk = n;
    for(int i=1; i<k; i++) //k个字符中，每一个字符都有n种选择，n^k表示所有由k个字符组成的字符串种数
        lk *= n;
    lk--;
    int *x = new int[n+1];
    for(int i=1; i<=n; i++)
        x[i] = i;
    Perm(x, 1, k, n); //将长度为k的全排列存入集合L中
    backtrack(0);
    cout << "\n最大无分隔符字典元素个数为：" << best;

    cout << endl;
    cout << endl;
    fin.close();
    return 0;
}

image-20230104103946623

5. 时间复杂度

考虑最坏情况，对于n个字符，长度为k的问题，对于每个非叶子节点的左子节点，搜索需要耗费时间为$O(n^kk)$，对于右子节点搜索需要的时间为$O(1)$，对于叶节点需要时间$O(1)$，故耗费的时间$T=O(2^{n^k-1}n^k*k)$

5-6 无合集问题

image-20230104103710037

大概的思路是从1开始每个数都尝试放入n个子集的每个子集，然后用题目给的条件x+y不属于S进行剪枝

1. 解空间和解结构

从1开始尝试放入每个子集中，对于子集为n的无合集问题，其解空间为长度为k的向量，向量的每一项为1~n，表示对应下标的数分配到的子集，其中k为本题所求，以n=3为例，解结构如下：

image-20230104111844462

2. 剪枝策略

据题意，若数i无法分配到集合j(不满足和不在集合的条件)，则该节点的第j个分支无需遍历，剪去该分支

3. 示例

image-20230104112758039

4. 代码

定义存储当前解的数组a[N][N],其中a[n][0]表示第n个子集的元素个数a[n][1]到a[n][a[n][0]]为这个子集的所有元素。定义n。设置初始的结果ans为1(最后要减1，所以初始值其实是0)，定义最优值为best，定义最优解为e[N][N]，其中的结构和a[N][N]一样,以及定义判定数组h[N][N]，h[i][j]表示第i个子集中是否有j这个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int a[N][N], n, ans = 1, best, e[N][N];
bool h[N][N];

void dfs(int level){                        //判断当前ans中的数是否能插入第level个子集
    if(level == n){                         //n个子集的下标是0到n-1,所以当level等于n时表示当前ans不能插入所有子集
        if(ans <= best) return;             //如果当前ans不如当前最优值best，就返回
        best = ans;                         //如果比最优值好，更新最优值和最优解
        for(int i = 0; i < n; i ++){
            for(int j = 0; j <= a[i][0]; j ++)
                e[i][j] = a[i][j];
        }
        return;
    }
    else{                                   //判断ans能否插入第level个子集
        bool flag = true;           
        for(int i = 1; i <= a[level][0]; i ++){//遍历子集
            //如果ans减当前元素在子集中且这个元素不是它本身,flag就为false,表示ans不能插入这个子集
            if(h[level][ans - a[level][i]] && ans - a[level][i] != a[level][i]) flag = false;
        }
        if(!flag) dfs(level + 1);           //不能插入，判断ans能不能插入第level+1个子集  
        else{                               //可以插入，分两种情况，一种是插入，一种是不插入此子集
            //插入的情况
            a[level][++ a[level][0]] = ans; //第i个子集个数加一，把元素记入子集
            h[level][ans ++] = true;        //把此元素标记为在此子集中
            dfs(0);                         //判断下一个数是否能插入第0个子集
            //回溯到不插入的情况，把子集个数减1，再把当前元素标记为不在此子集中
            -- a[level][0];                 
            h[level][-- ans] = false;
            dfs(level + 1);                 //判断这个数是否能插入下一个子集
        }
    }
}

int main()
{
    cin >> n;
    dfs(0);
    cout << --best << endl;                 //记录的是最优值加一，这里减去一并输出
     for(int i = 0; i < n; i ++){
            for(int j = 1; j <= e[i][0]; j ++)
                printf("%d ", e[i][j]);     //输出最优解
        puts("");
    }
    return 0;
}

参考：无和集问题 - AcWing

5. 时间复杂度

考虑最坏情况，对于非叶子节点，假设其位于第i层，则时间消耗为$O(i)$，对于非叶子节点，其时间消耗为$O(1)$,本题时间消耗还与树的层数有关，而层数又是要求的。。。，需要一些推导来得到一个上界吧~

5-7 n色方柱问题

image-20230104113608782

image-20230104113717884

为了提高效率，用图论的知识简化了题目（我没怎么看懂为啥这样简化的），谢谢有被恶心到

image-20230108094031142

image-20230108094127364

有点难懂，我觉得不会考。。。，理解一下代码吧

代码

input.txt:

1
2
3
4
5
6
4
RGBY
0 2 1 3 0 0
3 0 2 1 0 1
2 1 0 2 1 3
1 3 3 0 2 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

const int MAX = 50;
int board[MAX][6];  //存储n个立方体各面的颜色
int solu[MAX][6];   //存储解
int n;  //立方体个数、颜色种数
int ans = 0;  //解的个数
int used[MAX];
char color[MAX];

//找到一个解后，输出
void out(int edge[])
{
    int i, j, k, a, b, c, d;
    for(i=0; i<2; i++) //2个子图
    {
        for(j=0; j<n; j++)
            used[j] = 0;
        do{
            j = 0;
            d = c = -1;
            while(j<n && used[j]>0) //找下一条未用的边
                j++;
            if(j < n)
                do{
                    a = board[j][edge[i*n+j]*2];
                    b = board[j][edge[i*n+j]*2+1];
                    if(b == d)  //如果上一条边的终点与b相同，说明b为始点，交换，保证a为始点
                        swap(a, b);  //保证有向边的始点对应于前面和左面，终点对应于背面和右面
                    solu[j][i*2] = a;
                    solu[j][i*2+1] = b;
                    used[j] = 1;
                    if(c<0)  //开始顶点
                        c = a;
                    d = b;
                    for(k=0; k<n; k++)  //找下一个立方体
                        if(used[k]==0 && (board[k][edge[i*n+k]*2]==b || board[k][edge[i*n+k]*2+1]==b))
                            j = k;
                }while(b != c);  //找了一圈，回到起点
        }while(j<n);  //所有立方体都找遍
    }
    for(j=0; j<n; j++) //立方体的顶面和底面的颜色
    {
        k = 3 - edge[j] - edge[j+n];
        a = board[j][k*2];
        b = board[j][k*2+1];
        solu[j][4] = a;
        solu[j][5] = b;
    }
    for(i=0; i<n; i++)
    {
        for(j=0; j<6; j++)
            cout << color[solu[i][j]] << " ";
        cout << endl;
    }
}

void search()
{
    int i, t, cube;
    bool ok, newg, over;
    int *vert = new int[n];  //记录子图中每个顶点的度，应均为2
    int *edge = new int[n*2];  //记录每个立方体中边被选用的条数，每个立方体只有3条边，有两个子图要选用
    for(i=0; i<n; i++)
        vert[i] = 0;
    t = -1;
    newg = true;
    while(t > -2)
    {
        t++;
        cube = t % n;  //每个立方体找2次，得到真实的立方体编号，也是子图中边的编号
        if(newg)  //如果没有边被选入子图
            edge[t] = -1;
        over = false;  //是否结束，即两个子图构建完成
        ok = false;    //标记边是否已用过，两个子图不应有公共边
        while(!ok && !over)
        {
            edge[t]++;  //边被选用加入子图，使用次数增加
            if(edge[t]>2)  //在立方体每对相对面的顶点连一条边，每个立方体只有3条边
                over = true;
            else
                ok = (t<n || edge[t]!=edge[cube]);  //是否已用过
        }
        if(!over)
        {          //检测边的两个顶点的度
            if(++vert[board[cube][edge[t]*2]] > 2+t/2*2) //如果是第一个子图，顶点度不能超过2
                ok = false;              //如果是第二个子图，加上第一个子图，顶点度不能超过4
            if(++vert[board[cube][edge[t]*2+1]] > 2+t/2*2)
                ok = false;
            if(t%n == n-1 && ok)  //如果一个或两个子图已构建完成
                for(i=0; i<n; i++)
                    if(vert[i] > 2+t/n*2)
                        ok = false;
            if(ok)
            {
                if(t == n*2-1) //找到解
                {
                    ans++;
                    out(edge);
                    return;
                }
                else
                    newg = true;
            }
            else //取下一条边
            {
                --vert[board[cube][edge[t]*2]];  //边的两个顶点
                --vert[board[cube][edge[t]*2+1]];
                t--;
                newg = false;
            }
        }
        else //回溯
        {
            t--;
            if(t > -1)
            {
                cube = t % n;
                --vert[board[cube][edge[t]*2]];
                --vert[board[cube][edge[t]*2]];
            }
            t--;
            newg = false;
        }
    }
}

int main()
{
    ifstream fin("input.txt");
    cout << "输入立方体个数：";
    fin >> n;  cout << n;
    cout << "\n输入颜色：";
    for(int i=0; i<n; i++)
    {
        fin >> color[i];
        cout << color[i] << " ";
    }
    cout << "\n输入立方体各面颜色：\n";
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<6; j++)
        {
            fin >> board[i][j];
            cout << board[i][j] << " ";
        }
        cout << endl;
    }

    cout << "\n立方体叠置方案为：\n";
    search();
    if(ans == 0)
        cout << "No Solution！\n";
    cout << end;
    fin.close();
    return 0;
}

image-20230104115831309

5-8 整数变换问题

image-20230105102915399

这道题是一定能找到的，有点类似于3n+1?，要不然会要求输出no solution的，而且我们也不能简单地通过n和m的大小关系来得到此时需要做的操作。题目的思路大概就是DFS暴力搜索，左子树f变换，右子树g变换，主要问题在于需要限制搜索的层数，因为有些分支是得不到解的

1. 解空间和解结构

解空间是一个长度为k的向量，向量的每一项是f或者g，k的大小与输入有关，解结构如下：左子树是进行f变换，右子树是进行g变换。

image-20230105111327567

2. 剪枝策略

虽然看到一些博客根据n和m的大小剪枝，但是实际上在代码中他们没有这样做，而且这种做法应该是不对的。。。

我觉得这里更加类似于DFS，代码也没体现出什么剪枝的策略，这里的搜索过程有点像是一层一层往下搜索，k控制着层数

3. 示例

1
2
3
7 4
3
gfg

image-20230105113429567

4. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
#define N 25
#define inf 0x3f3f3f3f
int n, m;
//定义k来表示搜索树的深度
int k = 1;
//定义一个队列来存放各类操作
queue<char> q;
bool DFS(int x, int n)
{
    //防止死循环，保证最多只能访问到下一层
    if(x > k)
        return false;
    //找到返回true
    if(n == m)
        return true;
    //这里必须用一个temp做临时变量
    //若不用temp做临时变量，回溯的时候n的值发生变化
    //导致结果异常
    int temp = n;
    //左右都做一遍，看看能否到达目的
    for(int i = 0; i < 2; i++)
    {
        if(i == 0)
            temp = n * 3;
        else
            temp = n / 2;
        if(DFS(x+1, temp))
        {
            if(i == 0)
                q.push('f');
            else
                q.push('g');
            //这里必须要return true 
            //因为只需要找到第一个满足条件的那条路径
            //回溯返回的时候把路径上的运算加入队列即可。
            return true;
        }
    }
    //如果没找到返回false,k++
    //可往更深一层探索
    return false;
}
int main()
{
    cin >> n >> m;
    //找不到，往更深一层探索！
    while(!DFS(0, n))
        k++;
    cout << k << endl;
    while(!q.empty())
    {
        cout << q.front();
        q.pop();
    }
    return 0;
}

5. 时间复杂度

树的层数和输入的数关系比较大，不太好分析。。。，如果树的层数可以得到一个上界的话，可以推导一下最坏情况

参考：https://blog.csdn.net/Small___ming/article/details/103218990

5-9 拉丁矩阵问题

image-20230105113714306

可以从左到右从上到下来填充矩阵的每个“格子”，即树的每一层就是考虑每个格子里放什么，这将得到一棵比较大的树，剪枝的策略就是题目所要求的，每行每列都没有相同的形状，若在该格子里放入第i种宝石能满足要求，则将其放入，否则剪去该条分支，对于检查每行每列是否有相同形状，可以采用两个矩阵来记录，这样时间效率会高点

1. 解空间和解结构

本题是求可行解的个数，解空间是一个n行m列的矩阵，也可以理解为n*m长度的向量，其中向量的每个元素为1~n，对应的解结构为排列树

2. 剪枝策略

维护矩阵row[N][N]，其中row[i][j]=1表示第i行已经使用了形状j，矩阵col[N][N]，其中col[j][i]=1表示第i列使用了形状j，考虑在为矩阵(x,y)位置上元素选择宝石时，若选择宝石i，则需要保证row[x][i]==0&&col[i][y]==0，即不与x行和y列上已有的形状冲突，若不满足该条件，则可剪去该子树

3. 示例

image-20230105194002403

image-20230105194603562

4. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<stdio.h>
#define N 10
int m,n;    //分别为行、列
int count=0;
int a[N][N]={0};
int row[N][N]={0};
//row[i][j]=1表示第i行已经使用了形状j
int col[N][N]={0};
//col[j][i]=1表示第i列已经使用了形状j
void backtrack(int t)
//t表示正在填充的矩阵的一个小格子,格子范围为0~m*n-1
//如第一行就是0 1 2 3 4...
{
    int i,j;
    int x,y;    //分别为行、列（坐标）
    if(t==m*n)//如果排完了,说明得到了一种可行解
    {
        count++;
        return;
    }
    //否则继续排列
    x=t/n;      //行坐标
    y=t%n;      //列坐标
    for(i=1;i<=n;i++)//对每种形状都进行尝试
    {
        if(row[x][i]==0&&col[i][y]==0)
        {
           row[x][i]=1;
           col[i][y]=1;
           a[x][y]=i;
           backtrack(t+1);
           row[x][i]=0;//回溯
           col[i][y]=0;
           a[x][y]=0;
        }
    }
}

int main()
{
    scanf("%d%d",&m,&n);
    backtrack(0);
    printf("count=%d\n",count);
    return 0;
}

5. 时间复杂度

考虑最坏情况，对于叶子节点，其时间消耗为$O(1)$，对于非叶子节点其时间消耗为$O(n)$，对于n种宝石，排成n行m列的拉丁矩阵问题，时间消耗为$T=O(n^{mn})$

5-10 排列宝石问题

image-20230105114234838

这道题是类似于5-9的(直接在5-9上面改的几行)，说一下思路吧：类似于对待不同宝石类型要求每行每列都不重复，引入数组color_row和数组color_col，其大致结构和含义与row和col类似，用于记录该行或者该列是否已经使用过该种颜色的宝石，还引入used数组用于满足题中的每种宝石n颗且不同色（避免一种宝石的一种颜色使用了多次），其中used[i][j]=1表示类型i的宝石的第j种颜色已用。

与5-9对比，排列树可选的分支大大增加了，不过剪去的分支也比较多，时间复杂度往上蹭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define N 10
using namespace std;
int n;    //分别为行、列
int res=0;
int row[N][N]={0};
//row[i][j]=1表示第i行已经使用了形状j
int col[N][N]={0};
//col[j][i]=1表示第i列已经使用了形状j
int color_row[N][N]={0};
int color_col[N][N]={0};
int used[N][N]={0};//used[i][j]=1表示类型i的第j种颜色已用

void backtrack(int t)
//t表示正在填充的矩阵的一个小格子,格子范围为0~m*n-1
//如第一行就是0 1 2 3 4...
{
    int i,j;
    int x,y;    //分别为行、列（坐标）
    if(t==n*n)//如果排完了,说明得到了一种可行解
    {
        res++;
        return;
    }
    //否则继续排列
    x=t/n;      //行坐标
    y=t%n;      //列坐标
    for(i=1;i<=n;i++)//对每种形状都进行尝试
    {
        for(j=1;j<=n;j++){//j为颜色
        if(!row[x][i]&&!col[i][y]&&!color_row[x][j]&&!color_col[j][y]&&!used[i][j])
        {
           row[x][i]=1;
           col[i][y]=1;
           color_row[x][j]=1;
           color_col[j][y]=1;
           used[i][j]=1;
           backtrack(t+1);
           row[x][i]=0;
           col[i][y]=0;
           color_row[x][j]=0;
           color_col[j][y]=0;
           used[i][j]=0;
        }
        }
    }
}

int main()
{
    scanf("%d",&n);
    backtrack(0);
    printf("res=%d\n",res);
    return 0;
}

5-11 重复拉丁矩阵问题

image-20230105114335314

这题是类似于5-9的，我的代码一直没AC，参考了下答案的，思路是：第一行按照题意，由于对每行每种宝石数量的限制，且要求第一行最小字典序，所以是固定的，无需回溯，故从第二行开始进行搜索。答案遵照教材的排列树的写法，先初始化矩阵，然后再做swap操作，矩阵初始化情况如虚线上矩阵(示例为例)，在搜索的时候，只需要考虑每列宝石要求即可（因为初始化的原因，不需要考虑每行了），但是很奇怪的是，代码没有考虑第一列的情况了，即认为第一列也是固定的，但是我觉得不太对，比如虚线下面的一种也是可以的。

1
2
3
4
5
6
7
8
9
10
省略第0行、第0列
1 1 2 2 3 3 3
1 <1> 2 2 3 3 3
2 1 1 2 3 3 3
2 1 2 1 3 3 3
-------------
1 1 2 2 3 3 3 
3 3 3 2 2 1 1 
3 3 3 1 2 2 1 
3 3 2 1 3 1 2

input:

1
2
4 7 3
2 2 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

const int MAX = 50;
int n, m, k;
int times[MAX];  //每种宝石的重复次数
int id[MAX];  //每个宝石的价值序号
int board[MAX][MAX];  //宝石矩阵

//考察当前列宝石数是否多于应出现的次数
bool ok(int r, int c, int s)
{
    int k = board[r][s];
    int i;
    if(s > c)
        for(i=c; i<s; i++)
            if(board[r][i] == k) //如果已经试过相同类型的宝石，这次就不再试了
                return false;

    int count = 0;
    for(i=1; i<r; i++)  //考察当前列宝石数是否多于应出现的次数
        if(board[i][c] == k)
            count++;
    if(count >= times[k]) //times[k]表示种类为k的宝石应出现的次数
        return false;
    else
        return true;
}

double num = 0;  //不同的宝石排列方案数
//从上到下，从左到右递归搜索，即先行后列
void backtrack(int r, int c)
{
    for(int i=c; i<=n; i++)  //列
        if(ok(r, c, i))
        {
            swap(board[r][c], board[r][i]);
            if(c == n)  //如果列考察完毕
            {
                if(r == m) //如果行考察完毕
                {
                    num += 1;
                    //cout << num << " ";
                    return;
                }
                else
                    backtrack(r+1, 2); //考察下一行
            }
            else
                backtrack(r, c+1); //考察下一列
            swap(board[r][c], board[r][i]);
        }
}

int main()
{
    ifstream fin("input.txt");
    cout << "\n输入行数m：";
    fin >> m;  cout << m;
    cout << "\n输入列数n：";
    fin >> n;  cout << n;
    cout << "\n输入宝石价值种数：";
    fin >> k;  cout << k << endl;
    int i, temp;
    int t = 1;
    for(i=1; i<=k; i++)
    {
        cout << "输入第" << i << "种宝石在每行每列出现的最多次数：";
        fin >> times[i];
        cout << times[i] << "\n";

        temp = times[i];
        while(temp>0)
        {
            id[t++] = i;
            temp--;
        }
    }

    int j;
    for(i=1; i<=m; i++)  //初始化为单位矩阵
        for(j=1; j<=n; j++)
            board[i][j] = id[j];
    //第一行已经排列好了,无需再改变了
    
    /*
    由于初始化后的单位矩阵的第一列都是1，为使矩阵的第一列同时满足一下两个条件： 
    同一种宝石数都不超过规定的数量，第1列从上到下的宝石按宝石的价值最小字典序从小到大排列 
    将第i行的第一个宝石与它同行的第i个宝石交换位置
    */
    for(i=2; i<=n; i++)
        swap(board[i][1],board[i][i]);
    backtrack(2, 2);
    cout << "\n不同的宝石排列方案数为：" << num;
    cout << endl << endl;
    return 0;
}

下面是我的代码，在5-9基础上改的，输出的文件out.txt是所有的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
#define N 10
using namespace std;
int m,n,k;    //分别为行、列
int res=0;
int a[N][N]={0};
int row[N][N]={0};
//row[i][j]=1表示第i行已经使用了形状j
int col[N][N]={0};
//col[j][i]=1表示第i列已经使用了形状j
int maxtime[N]={0};
void backtrack(int t,ofstream&out)
//t表示正在填充的矩阵的一个小格子,格子范围为0~m*n-1
//如第一行就是0 1 2 3 4...
{
    int x,y;    //分别为行、列（坐标）
    if(t==m*n)//如果排完了,说明得到了一种可行解
    {
        res++;
        out<<"---"<<res<<endl;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                out<<a[i][j]<<" ";
            }
            out<<endl;
        }
        out<<endl;
        return;
    }
    //否则继续排列
    x=t/n;      //行坐标
    y=t%n;      //列坐标
    for(int i=1;i<=k;i++)//对每种形状都进行尝试
    {
        bool flag=true;
        if(x==0&&y>0&&i<a[x][y-1]) flag=false;
        if(y==0&&x>0&&i<a[x-1][y]) flag=false;
        if(flag&&row[x][i]<maxtime[i]&&col[i][y]<maxtime[i])
        {
           //cout<<maxtime[i]<<": "<<row[x][i]<<","<<col[i][y]<<"| "<<res<<endl;
           row[x][i]++;
           col[i][y]++;
           a[x][y]=i;
           backtrack(t+1,out);
           row[x][i]--;//回溯
           col[i][y]--;
           a[x][y]=0;
        }
    }
}

int main()
{
    ofstream out;
    out.open("out.txt");
    scanf("%d%d%d",&m,&n,&k);
    for(int i=1;i<=k;i++) scanf("%d",&maxtime[i]);
    backtrack(0,out);
    printf("res=%d\n",res);
    out.close();
    return 0;
}

5-12 罗密欧与朱丽叶的迷宫问题

image-20230105115004711

image-20230105114937912

从罗密欧的位置开始，每次都可以走八个方向，用数字记录方向，若下一次走的方向与直接的不同则记转向次数加一，在考虑进入八个方向的下一位置前，需要考虑该位置是否越界，是否是封闭位置，是否已经走过，且是否走入后当前转向次数大于当前最优解此时，以此作为剪枝策略，当遍历完所有的位置后，若到达了朱丽叶的位置，则考虑更新当前最优解或者是增加最优解的次数

1. 解空间和解结构

对于n行m列，封闭房间数为k的迷宫，迷宫问题的解空间为1~n*m-k的全排列，表示某个房间第几次到达，解结构为排列树

2. 剪枝策略

约束函数：在尝试走入下一位置前，检查该位置是否合法，即是否数组越界，是否为封闭房间，是否已经走过，若不合法，则剪去该子树

限界函数：维护变量curr_rotation表示当前转向次数，min_rotation表示当前最优解的转向次数，若在考虑下一位置时，到达该位置后的转向次数大于最优解的转向次数，则剪去该子树

3. 代码

input:

1
2
3
4
5
3 4 2
1 2
3 4
1 1
2 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <bits/stdc++.h>
using namespace std;
struct Point
{
	int x, y;
};
Point luo;
Point ye;
Point pos;

//	定义八个方向:右,
int dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 }; //八个方向
int dy[8] = { 0, 1, 0, -1, 1, -1, 1, -1 };

const int MAX = 10;
int n, m, k;
int board[MAX][MAX];
int best[MAX][MAX];
int curr_rotation = 0;  //转弯次数
int min_rotation = 100000;   //最少转弯次数
int min_count = 0;  //不同的最少转弯道路数
bool flag = false;


bool Point_check(Point pos) {
	if (pos.x > 0 && pos.x <= n && pos.y > 0 && pos.y <= m && board[pos.x][pos.y] == 0)
		return true;
	return false;
}

//	更新当前最少转弯情况下的路线
void upgrade() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			best[i][j] = board[i][j];
	flag = true;
}



//	回溯算法--->形式参数表示的是traceBack的层数
void  traceBack(int depth, Point pos, int di) {
	/*
		回溯法的终止条件，
		当把所有的空房间都遍历一遍
		且当前到达的位置是朱丽叶的位置
		且当前转弯的次数少于等于历史的次数
	*/
	if (depth == m * n - k && pos.x == ye.x && pos.y == ye.y && curr_rotation <= min_rotation) {
		/*
			如果当前的curr_count小于min_rotation更新min_rotation、min_count以及路径图
		*/
		if (curr_rotation < min_rotation) {//有更少的转向
			min_rotation = curr_rotation;
			min_count = 1;//重新计数


			//	更新路径图
			upgrade();
		}
		else {
			min_count++;
		}
		return;
	}
	else {
		//	剪枝策略-----当到达这个位置的时候curr_rotation已经大于min_rotation那么进行剪枝
		for (int i = 0; i < 8; i++) {

			//	通过走的方向，计算下一个位置
			Point next_pos;
			next_pos.x = pos.x + dx[i];
			next_pos.y = pos.y + dy[i];

			//	每次走一步需要判断你下一个地点的位置是否合法
			if (Point_check(next_pos)) {
				board[next_pos.x][next_pos.y] = depth + 1;

				if (depth > 1 && di != i)
					curr_rotation++;

				if (curr_rotation <= min_rotation)
					traceBack(depth + 1, next_pos, i);

				//	进行回溯
				board[next_pos.x][next_pos.y] = 0;
				if (depth > 1 && di != i)
					curr_rotation--;
			}
		}
	}
}



int main() {

	//	迷宫的初始化
	memset(board, 0, sizeof(board));

	memset(best,0,sizeof(board));


	//	文件的输入
	ifstream datain("input.txt");

	cout << "输入迷宫的宽度："; datain >> n; cout << n<<endl;

	cout << "\n输入迷宫的长度："; datain >> m; cout << m << endl;

	cout << "\n输入封闭房间个数："; datain >> k; cout << k << endl;

	//	封闭房间数据的输入
	Point forbidden_rooms;
	for (int i = 0; i < k; i++) {
		datain >> forbidden_rooms.x >> forbidden_rooms.y;
		board[forbidden_rooms.x][forbidden_rooms.y] = -1;
	}

	//	输入罗密欧和朱丽叶的位置信息
	datain >> luo.x >> luo.y;
	cout << endl << "罗密欧位置坐标：[" << luo.x << ", " << luo.y << "]" << endl;

	board[luo.x][luo.y] = 1;//起始位置

	datain >> ye.x >> ye.y;
	cout << endl << "朱丽叶位置坐标：[" << ye.x << ", " << ye.y << "]" << endl;

	//	回溯算法开始
	traceBack(1, luo, 0);


	//	把结果输出到txt文件中
	ofstream dataout("output_data1.txt", ios::trunc);

	if (flag) {
		cout << "\n最小转弯次数：" << min_rotation << endl;
		cout << "\n最小转弯次数的转弯道路数：" << min_count << endl;
		cout << "行走的路线图：" << endl;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << best[i][j] << " ";
			}
			cout << endl;
		}
	}
	else {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				cout << board[i][j] << " ";
			}
			cout << endl;
		}
		cout<< "\nNo Solution!" << endl;
	}

	return 0;
}

5-13 工作分配问题

image-20230105114617529

由于每个工作仅由一人完成，每个人仅做一个工作，对于示例的输入矩阵，所求即为在每一行取一个数，且保证所取数不在同一列，求他们的和最小值，易知如果用暴力解法，设矩阵的行数为n，则解为n个数的排列组合，其中第i个数表示第i个工作分配给第j个人，则对于上述输入矩阵，可以得到可行解（3,2,1），（2,1,3），……

1. 解空间和解结构

对于n个工作的工作分配问题，其解空间即为1~n的全排列，解结构为排列树，具体而言树的第i层表示第i个工作的分配，每层的顶点表示该工作分配的人，如红色方框框出的节点即表示第1个工作分配给C1

image-20230106091616647

2. 剪枝策略

在搜索的过程中记录当前费用cv和最优费用bestv,若cv大于等于bestv，则无需再遍历该节点的子树（因为向下搜索的过程费用一定是单调递增的）

3. 示例

分成两幅图来画了，实际上是一幅图

image-20230106091745691

image-20230106091753460

4. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
const int N=10010;
int num;
int Min=INT_MAX;
int arr[N][N];
int sum=0;
int state[N];

void dfs(int t)//从第t层开始搜索
{
    if(t>=num) //已经到达叶子节点，继续判断是否找到了最小总费用
    {
        if(Min>sum)//若当前费用小于最优费用
        {
            Min=sum;//更新最优费用
            return;
        }
    }
    for(int i=0;i<num;i++)//搜索过程:将作业t进行分配
    {
        if(!state[i])//若第i个人当前无作业
        {
            state[i]=1;//将任务t分配给第i个人
            sum+=arr[t][i];//更新当前费用
            if(sum<Min) dfs(t+1);//若当前费用小于最优费用,则继续向下搜索
            state[i]=0;//回溯,恢复原状态
            sum-=arr[t][i];//将当前费用恢复
        }
    }
}
int main()
{
    ifstream in;
    ofstream out;
    in.open("input.txt");
    out.open("output.txt");
    in>>num;
    Min=INT_MAX;
    sum=0;
    for(int i=0;i<num;i++)
    {
        for(int j=0;j<num;j++)
        {
            in>>arr[i][j];
        }
        state[i]=0;
    }
    dfs(0);
    cout<<"最小费用为："<<Min<<endl;
    out<<"最小费用为："<<Min<<endl;
    in.close();
    out.close();
    return 0;
}

5. 时间复杂度

考虑最坏情况，对于非叶子节点，其搜索所需时间为$O(n)$，对于叶子节点，其搜索所需时间为$O(1)$，故对于n个工作的工作分配问题，其时间消耗$T=n(n+nn-1+…+n!)+n!=O(n!*n)$

5-14 布线问题

image-20230105114815154

经典排列树，然后剪枝策略可以维护一个当前最优解的成本，若当前成本大于等于该变量，则剪去该分支。

1
2
3
3
2 3
3

1. 解空间和解结构

对于n个元件的布线问题，其解空间为1~n的全排列，解结构为排列树

2. 剪枝策略

维护当前最优解的成本bestv和当前费用cv，在考虑线路板t位置上是否放置元件i时，若当前费用加上放置元件i所带来的成本小于当前最优解的成本，则可继续搜索，否则剪去该分支

3. 示例

image-20230106111415596

4. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
const int N=25;
int n;
int conn[N][N];
int bestx[N];
int bestv=INT_MAX;
int cv;
int cx[N];
int currentvalue(int cx[],int t)//计算cx第t位带来的成本
{
    int res=0;
    for(int i=0;i<t;i++)//t是从0开始的
    {
        res=res+conn[cx[i]][cx[t]]*(t-i);//cx从0开始
    }
    return res;
}
void traceback(int t)
{
    if(t==n)//到达叶子节点
    {
      if(cv<bestv)
      {
          for(int i=0;i<n;i++)
          {
              bestx[i]=cx[i];
          }
          bestv=cv;
      }
      return;
    }
    for(int i=t;i<n;i++)//cx从0开始
    {
        swap(cx[t],cx[i]);
        int value=currentvalue(cx,t);//计算t这一位带来的成本
        if(value+cv<bestv)//满足限界条件
        {
            cv+=value;
            traceback(t+1);
            cv-=value;
        }
        swap(cx[t],cx[i]);
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            cin>>conn[i][j];//构造领接矩阵
            conn[j][i]=conn[i][j];//补全另一半
        }
    }
    for(int i=0;i<n;i++) cx[i]=i+1;//当前解,先初始化为123...
    traceback(0);
    cout<<bestv<<endl;
    for(int i=0;i<n;i++)
        cout<<bestx[i]<<" ";
    return 0;
}

5. 时间复杂度

考虑最坏情况，对于n个元件的布线问题，对于非叶子节点，其消耗的时间与其层数t有关，为$O(n-t)$,对于叶子节点，其消耗的时间为$O(n)$，故该问题时间消耗为:$T=nn+n(n-1)(n-1)+n(n-1)(n-2)(n-2)+…+n!+n!n=O(n!n)$

5-15 最佳调度问题

image-20230105115631677

可以一一为每个任务分配工作，每个任务都可以尝试分配给每台机器，从而对排列树进行搜索。用一个数组存储每台机器已经分配的任务的总耗时，搜索到可行解后这个数组中的最大值即为当前解所需时间，在剪枝的过程中，将更新后该数组的值（即表示选择分配给该机器）与当前最优解的耗时比较，若小于则可继续搜索。

1. 解空间和解结构

对于n个任务k台机器的最佳调度问题，其解空间为长度为n的向量，向量的每一项为1~k，解结构为排列树

2. 剪枝策略

按照题意，要求完成全部任务的时间最早，故维护变量mintime表示当前最优解的完成时间，数组ans存储每台机器完成当前任务后的时间，在任务分配过程中，尝试将任务i分配给机器j，若t[i]+ans[j]>=mintime，则将该分支剪去，无需再搜索

3. 代码

1
2
7 3
2 14 4 16 6 5 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<algorithm>
using namespace std;
int n,k,t[99],ans[99],min_time=0x3f3f3f3f;
//ans[i]表示第i个机器运行完其上任务后的时间
//t[i]表示第i个任务需要的时间
void dfs(int level)
{
	if(level==n)
	{
		int tmp=*max_element(ans,ans+n);//max_element找数组的最大值
		if(tmp<min_time) min_time=tmp;
		return;
	}
	for(int i=0;i<k;i++)//尝试分配给第i台机器
	{
		ans[i]+=t[level];
		if(ans[i]<min_time) dfs(level+1);
		ans[i]-=t[level];
	}
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	cin>>t[i];
	dfs(0);
	cout<<min_time<<endl;
}

4. 时间复杂度

考虑最坏情况，对于非叶子节点，其时间消耗为$O(k)$，对于叶子节点，其时间消耗为$O(n)$，故对于n个任务k台机器的最佳调度问题，其时间消耗为$T=k(k+k^2+…+k^{n-1})+nk^n=O(n*k^n)$

5-16 无优先级运算问题

image-20230105115723106

有点类似于整数变换问题，这里也是不知道树的层数，可以从1个数，2个数，…,n个数逐步增加树的层数，在选择数的时候，只能使用未选过的数，以此作为剪枝策略（可以用过数组记录某个数是否选过），使用数组记录该数右侧的运算符，每种符号的选择均作为分支向下搜索，当到达叶子节点时，检查当前运算结果是否为m，若为m，则不继续搜索，程序结束

1. 解空间和解结构

对于n个正整数的无优先级运算问题，其解空间为长度为2k-1(k从1到n)的向量，该向量的每一个奇数项为1~n的数且相互之间不重复，偶数项为1、2、3、4，分别表示+,-,*,\，解的结构为排列树，具体而言如下所示：

image-20230106212553925

2. 剪枝策略

维护数组flag表示n个数是否使用，flag[i]=1表示第i个数已经使用，当给第dep位数选择数时，若该数已经使用过，则无法选择，剪去该分支

3. 代码

1
2
5 25
5 2 3 6 7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>

using namespace std;
const int N=100;
int n,m;
int a[N];//存储题目所给n个数
int num[N];//存储当前解
int oper[N];//num[i] oper[i] num[i+1]
int flag[N];//存储i个数的状态，是否使用
int k;//表示使用的数的个数
bool found(){//判断是否找到解
    int x=num[0];
    for(int i=0;i<k;i++)
    {
        switch(oper[i]){
        case 0:x+=num[i+1]; break;
        case 1:x-=num[i+1]; break;
        case 2:x*=num[i+1]; break;
        case 3:x/=num[i+1]; break;
        }
    }
    return (x==m);
}
bool traceback(int dep)//考虑第dep个数
{
    if(dep>k){
        if(found()) return true;
        else return false;
    }
    for(int i=0;i<n;i++)//第dep个数尝试选择数i
    {
        if(flag[i]==0)
        {
            num[dep]=a[i];
            flag[i]=1;
            for(int j=0;j<4;j++)//选择该数右边的符号
            {
                oper[dep]=j;
                if(traceback(dep+1))
                    return true;
            }
            flag[i]=0;
        }
    }
    return false;
}
void out()//输出函数
{
    for(int i=0;i<k;i++)
    {
        cout<<num[i];
        switch(oper[i]){
            case 0:cout<<"+";break;
            case 1:cout<<"-";break;
            case 2:cout<<"*";break;
            case 3:cout<<"/";break;
        }
    }
    cout<<num[k];
    return;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        flag[i]=0;
    }
    for(k=1;k<=n;k++)
    {
        if(traceback(0))
        {
            cout<<k<<endl;
            out();
            return 0;
        }
    }
    cout<<"No Solution!"<<endl;
    return 0;
}

4. 时间复杂度

考虑最坏情况，需要n个数，每个非叶子节点的时间消耗为$O(n)$，每个叶子节点的时间消耗为$O(n)$，此时时间消耗为$T=n(1+n+4n+4n^2+4^2n^2+…+4^{n-1}n^{n})=O(n^nn4^{n-1})$，真的很大。。。

5-17 世界名画陈列馆问题

image-20230105115824426

input:

1
4 4

output:

1
2
3
4
5
4 
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

这题的思路参考了书的答案，他的剪枝策略有点复杂

1. 解空间和解结构

解空间为长度为n*m的向量，向量的每一项为0或者1，表示是否放置警卫，解结构为子集树

2. 剪枝策略

  1. 可以证明,当前访问的格点(i,j)已被监视时,放置在(i,j)的情况一定不会比放置在(i+1,j+1)的情况好.当(i+1,j+1)不在网格中时,(i+1,j)和(i,j+1)同理.所以,如果(i,j)已被监视,则不需要在此处放置机器人,直接跳过即可.（update,证明：因为是从上到下从左到右使得格子进入监视状态，当前正在检查访问(i,j)。说明在这之前的(i-1,j)和(i,j-1)已被监视。此时如果放在(i,j)处，只会使得(i+1,j)和(i,j+1)进入访问状态。而如果放在(i+1,j+1)处，显然在完成上述目标的情况下可以使更多格子进入访问状态）
  2. 当(i,j)未被监视时,若(i,j+1)已被监视,则在(i,j)放置一定不会比在(i+1,j)放置的情况好.所以当且仅当(i,j)在网格右下角或者(I,j+1)未被监视时才考虑放置在(i,j)的情况.
  3. 当(i,j)未被监视时,若(i,j+1)和(i,j+2)均被监视,则在(i+1,j)放置一定不会比在(i+1,j)放置的情况好,所以当且仅当(i,j+1)或(i,j+2)未被监视时才考虑放置在(i,j+1)的情况.
  4. 当i=n时,不考虑放置在(i+1,j)的情况.
  5. 记录已经监视的格点数,(当前最优值减去当前已放置个数)*5如果小于未监视的格点数,则一定达不到比当前最优值更好的情况,剪去.
  6. 类似于(5),考虑更紧的情况,并非每个机器人都能独立监视5个格点,至少会有m/4+5的冗余,这个剪枝仅适用于i<n-1的情况,因为最后两行由于最优值和已放置个数非常接近,总是达不到这个值.

大概就是分为下界剪枝法和控制剪枝法两种，下界剪枝法就是计算剩余需要的警卫数，然后加上当前警卫数和当前最优解警卫数比较，控制剪枝法就是一堆已经证明的放置策略，如2、3、4,

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>

using namespace std;
const int N=100;
int d[6][3]={{0,0,0},{0,0,0},{0,0,-1},{0,-1,0},{0,0,1},{0,1,0}};
//d是个辅助用来改变状态的数组,从第1项开始,对应本身,左,上,右,下
int x[N][N];//当前的放置策略
int y[N][N];//是否受监视
int bestx[N][N];//最优放置策略
int n,m,best,k=0,t=0,t1,t2,more;
//k为当前警卫数量
//t为当前受监视的位置的个数
bool p;
void place(int i,int j)//在(i,j)处放置警卫,改变相邻位置的监视情况
{
    x[i][j]=1;
    k++;
    for(int s=1;s<=5;s++)
    {
        int p=i+d[s][1];
        int q=j+d[s][2];
        y[p][q]++;
        if(y[p][q]==1) t++;
    }
}
void noplace(int i,int j)//用于撤销在(i,j)上放置的警卫
{
    x[i][j]=0;
    k--;
    for(int s=1;s<=5;s++)
    {
        int p=i+d[s][1];
        int q=j+d[s][2];
        y[p][q]--;
        if(y[p][q]==0) t--;
    }
}
void traceback(int i,int j)
{
    do{
        j++;
        if(j>m){
            i++;
            j=1;
        }
    }while(!(y[i][j]==0||i>n));
    //若当前坐标未受监视或全部坐标都受到监视跳出循环
    if(i>n){
        if(k<best){
            best=k;
            for(int i=1;i<=m;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    bestx[i][j]=x[i][j];
                }
            }
        }
        return;
    }
    if(k+(t1-t)/5>=best)//利用k和t估计警卫下界,
        return;
    if((i<n-1)&&(k+(t2-t)/5)>=best)//也是利用k和t估计下界
        return;
    if(i<n){//下侧放警卫
        place(i+1,j);
        traceback(i,j);
        noplace(i+1,j);
    }
    if(j<m&&(y[i][j+1]==0||y[i][j+2]==0)){
        place(i,j+1);//在右侧放警卫
        traceback(i,j);
        noplace(i,j+1);
    }
    if((y[i+1][j]==0&&y[i][j+1]==0))
    {
        place(i,j);//在本身放警卫
        traceback(i,j);
        noplace(i,j);
    }
}
void output()
{
    cout<<best<<endl;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<bestx[i][j]<<" ";
        }
        cout<<endl;
    }
}
void solve()
{
    //下界剪枝法的辅助，主要是用来辅助通过t和k估计警卫人数的下界的
    more=m/4+1;
    if(m%4==3)
        more++;
    else if(m%4==2)
        more+=2;
    t2=m*n+more+4;
    t1=m*n+4;
	//下面就很好看懂了
    best=INT_MAX;
    memset(y,0,sizeof(y));
    memset(x,0,sizeof(x));
    if(n==1&&m==1)
    {
        cout<<1<<endl<<1<<endl;
        return;
    }
    //构造边界
    for(int i=0;i<=m+1;i++)
    {
        y[0][i]=1;
        y[n+1][i]=1;
    }
    for(int i=0;i<=n+1;i++)
    {
        y[i][0]=1;
        y[i][m+1]=1;
    }
    traceback(1,0);
    output();
}
int main()
{
    cin>>m>>n;
    solve();
    return 0;
}

5-18 世界名画陈列馆问题（不重复监视）

image-20230105115900644

在5-17上改了下，框架没变，去掉了答案那些控制剪枝法的剪枝策略，加上了题目中要求的不重复监视的剪枝策略，且在叶子节点处加上了对整个矩阵检查是否全部监视了，主要加了check函数，checkall函数，改了traceback函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>

using namespace std;
const int N=100;
int d[6][3]={{0,0,0},{0,0,0},{0,0,-1},{0,-1,0},{0,0,1},{0,1,0}};
//d是个辅助用来改变状态的数组,从第1项开始,对应本身,左,上,右,下
int x[N][N];//当前的放置策略
int y[N][N];//是否受监视
int bestx[N][N];//最优放置策略
int n,m,best,k=0,t=0,t1,t2,more;
//k为当前警卫数量
//t为当前受监视的位置的个数
bool p;
void place(int i,int j)//在(i,j)处放置警卫,改变相邻位置的监视情况
{
    x[i][j]=1;
    k++;
    for(int s=1;s<=5;s++)
    {
        int p=i+d[s][1];
        int q=j+d[s][2];
        y[p][q]++;
        if(y[p][q]==1) t++;
    }
}
bool check(int i,int j)//检查(i,j)是否能放置警卫
{
    for(int s=1;s<=5;s++)
    {
        int p=i+d[s][1];
        int q=j+d[s][2];
        if(y[p][q])
        {
            return false;
        }
    }
    return true;
}
bool checkall()//检查是否全部都有警卫
{
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!y[i][j]) return false;
        }
    }
    return true;
}
void noplace(int i,int j)//用于撤销在(i,j)上放置的警卫
{
    x[i][j]=0;
    k--;
    for(int s=1;s<=5;s++)
    {
        int p=i+d[s][1];
        int q=j+d[s][2];
        y[p][q]--;
        if(y[p][q]==0) t--;
    }
}
void traceback(int i,int j)
{
    do{
        j++;
        if(j>m){
            i++;
            j=1;
        }
    }while(!(y[i][j]==0||i>n));
    //若当前坐标未受监视或全部坐标都受到监视跳出循环
    if(i>n){
        if(k<best&&checkall()){
            best=k;
            for(int i=1;i<=m;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    bestx[i][j]=x[i][j];
                }
            }
        }
        return;
    }

    if(k+(t1-t)/5>=best)//利用k和t估计警卫下界,
        return;
    if((i<n-1)&&(k+(t2-t)/5)>=best)//也是利用k和t估计下界
        return;

   if(check(i,j))
   {
       place(i,j);
       traceback(i,j);
       noplace(i,j);
   }
   traceback(i,j);
}
void output()
{
    cout<<best<<endl;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<bestx[i][j]<<" ";
        }
        cout<<endl;
    }
}
void solve()
{
    more=m/4+1;
    if(m%4==3)
        more++;
    else if(m%4==2)
        more+=2;
    t2=m*n+more+4;
    t1=m*n+4;
	//下面就很好看懂了
    best=INT_MAX;
    memset(y,0,sizeof(y));
    memset(x,0,sizeof(x));
    if(n==1&&m==1)
    {
        cout<<1<<endl<<1<<endl;
        return;
    }
    traceback(1,0);
    output();
}
int main()
{
    cin>>m>>n;
    solve();
    return 0;
}

5-19 算m点问题

image-20230105115926418

类似于5-16，但是这里一定用到了k个整数，所以只需要稍微改改(把k设置为n-1然后改输出)，而且这种计算方式可以看成是无优先级的

示例应该给错了，应该是下面这样：

1
2
5 125
7 2 2 12 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>

using namespace std;
const int N=100;
int n,m;
int a[N];//存储题目所给n个数
int num[N];//存储当前解
int oper[N];//num[i] oper[i] num[i+1]
int flag[N];//存储i个数的状态，是否使用
int k;//表示使用的数的个数
bool found(){//判断是否找到解
    int x=num[0];
    for(int i=0;i<k;i++)
    {
        switch(oper[i]){
        case 0:x+=num[i+1]; break;
        case 1:x-=num[i+1]; break;
        case 2:x*=num[i+1]; break;
        case 3:x/=num[i+1]; break;
        }
    }
    return (x==m);
}
bool traceback(int dep)//考虑第dep个数
{
    if(dep>k){
        if(found()) return true;
        else return false;
    }
    for(int i=0;i<n;i++)//第dep个数尝试选择数i
    {
        if(flag[i]==0)
        {
            num[dep]=a[i];
            flag[i]=1;
            for(int j=0;j<4;j++)//选择该数右边的符号
            {
                oper[dep]=j;
                if(traceback(dep+1))
                    return true;
            }
            flag[i]=0;
        }
    }
    return false;
}
void out()//输出函数
{
    int ans=num[0];
    for(int i=0;i<k;i++)
    {
        cout<<ans;
        switch(oper[i]){
            case 0:cout<<"+";ans+=num[i+1];break;
            case 1:cout<<"-";ans-=num[i+1];break;
            case 2:cout<<"*";ans*=num[i+1];break;
            case 3:cout<<"/";ans/=num[i+1];break;
        }
        cout<<num[i+1]<<"="<<ans<<" ";
    }
    return;
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        flag[i]=0;
    }
    k=n-1;
    if(traceback(0))
    {
        out();
        return 0;
    }
    cout<<"No Solution!"<<endl;
    return 0;
}

image-20230106220815943

5-20 部落卫队问题

image-20230105120010640

image-20230105120024040

类似于0-1背包问题，子集树，左子树为1，右子树为0,约束函数就是不能和当前卫队里已有的居民为仇敌，若为仇敌，则剪去左子树。限界函数是当前卫队里的人数加上除去当前考虑的居民的剩余的居民，若数量还是比best小，则剪去右子树

1. 解空间和解结构

对于n个居民的部落卫队问题，其解空间为长度为n的向量，向量的每一项为0或者1，解结构为子集树

2. 剪枝策略

考虑居民t是否加入卫队，加入卫队即进入左子树，否则进入右子树

约束函数：若居民t和1~t-1中已经加入卫队的居民直接有仇视关系，则t不能加入卫队，剪去左子树

限界函数：若居民t不加入卫队，维护变量cv为当前卫队中居民人数，则卫队未来可能的最多人数为cv+n-t，若该值大于n，才搜索右子树，否则剪去右子树

3. 代码

input：

1
2
3
4
5
6
7
8
9
10
11
7 10
1 2
1 4
2 4
2 3
2 5
2 6
3 5
3 6
4 5
5 6

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>

using namespace std;
const int N=100;
int n,m;//n个居民,m个关系
int relation[N][N];//居民关系,0表示正常，1表示仇视,从1开始的
int cbest=0;//最多的卫兵
int bestx[N];//存储最优解
int cv=0;//当前卫兵人数
int x[N];//当前解,x[i]=1表示第i个居民是卫兵
void traceback(int t)//第t个居民是否作为卫兵
{
    if(t==n)//到达叶子节点
    {
        if(cv>cbest)
        {
            for(int i=0;i<n;i++)
            {
                bestx[i]=x[i];
                cbest=cv;
            }
        }
        return;
    }
    bool flag=true;//判断是否有冲突
    for(int i=0;i<t;i++)
    {
        if(x[i]==1&&relation[t+1][i+1]==1)
        {
            flag=false;
            break;
        }
    }
    if(flag)//考虑是否进入左子树
    {
        x[t]=1;
        cv++;
        traceback(t+1);
        x[t]=0;
        cv--;
    }
    if(cv+n-t>cbest)//考虑是否进入右子树
    {
        traceback(t+1);
    }
}
int main()
{
    cin>>n>>m;
    int t1,t2;
    for(int i=0;i<m;i++)//构造领接矩阵
    {
        cin>>t1>>t2;
        relation[t1][t2]=1;
        relation[t2][t1]=1;
    }
    traceback(0);//从第0个居民开始考虑
    cout<<cbest<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<bestx[i]<<" ";
    }
    return 0;
}

image-20230106230008395

4. 时间复杂度

考虑最坏情况，对于非叶子节点，搜索所需时间为$O(t+1)$，其中t为当前的层数，对于叶子节点，其搜索所需时间为$O(n)$，故居民数量为n的部落卫队问题的时间复杂度为$O(n*2^n)$

5-21、5-22

装载问题和0-1背包问题，见书上例题~

5-23 圆排列问题

image-20230106231319219

排列树，在选择一个圆的时候，就能计算他带来的长度（需要单独考虑第一个和最后一个的半径带来的长度），维护当前最优解，若当前解小于最优解才继续搜索，看看代码大概就能懂啦（突然发现书上有这道例题，也可以看看书上的）

1
2
3
1 1 2

1. 解空间和解结构

n个圆的圆排列问题的解空间为1~n的全排列，解结构为排列树

2. 剪枝策略

维护变量minlen表示当前最优解的长度，clen表示当前长度，当考虑放置第t个圆时，计算其带来的长度l，若l+clen>=minlen，则剪去该子树

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>

using namespace std;
const int N=100;
int n;
double r[N];
double minlen=DBL_MAX;
double clen=0;
int x[N];//当前的排列
double bring(int t)
{
    if(t==0) return r[x[t]];//第一个就是半径
    else{//加上t和t-1位置上圆心的x之间的距离
        double res=0;
        res=sqrt((r[x[t]]+r[x[t-1]])*(r[x[t]]+r[x[t-1]])-abs(r[x[t]]-r[x[t-1]])*abs(r[x[t]]-r[x[t-1]]));
        if(t==n-1) res+=r[x[t]];//最后一个还要加半径
        return res;
    }
}
void traceback(int t)//考虑放置的第t个圆
{
    if(t==n)//叶节点，更新min
    {
        if(clen<minlen) minlen=clen;
        return;
    }
    for(int i=t;i<n;i++)//考虑将未使用的圆放在t位置
    {
        swap(x[t],x[i]);
        double ctmp=clen;
        if(clen+bring(t)<minlen)//当前长度小于最优解长度
        {
            clen=clen+bring(t);
            traceback(t+1);
            clen=ctmp;
        }
        swap(x[t],x[i]);t
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>r[i];
        x[i]=i;
    }
    traceback(0);
    cout<<minlen;
    return 0;
}

4. 时间复杂度

考虑最坏情况，对于非叶子节点，搜索所需时间为$O(n-t)$，t为叶子节点的层数，对于叶子节点，搜索所需时间为$O(1)$，故n个圆的圆排列问题的最坏情况下时间复杂度为$O(n!)$

5-24

图着色问题，见书上例题~

5-25 最短加法链问题

image-20230105120329010

类似于整数变换那题，也是树的层数未知，所以可以用变量控制层数慢慢加大，可以采用无优先级运算问题的类似框架去解这道题，不同的是这题随着层数的加大分支数也加大了，剪枝策略是当前考虑的项不能大于23，看看代码就差不多~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;
const int N=100;
int n;//需要得到的数
int x[N];//加法链数组
int k;//控制层数
bool traceback(int t)//考虑加法链的第t项
{
    if(t==k)
    {
        if(x[k-1]==n) return true;
        else return false;
    }
    //选择加法链中的两个相加得到第t项
    for(int i=0;i<t;i++)
    {
        for(int j=0;j<t;j++)
        {
            if(x[i]+x[j]<=n)//剪枝，该项要小于等于n
            {
                x[t]=x[i]+x[j];
                if(traceback(t+1))
                {
                    return true;
                }
            }
        }
    }
    return false;
}
int main()
{
    cin>>n;
    x[0]=1;
    for(k=1;k<=n;k++)//最多n层
    {
        if(traceback(1))//这里得是1,因为如果是0会直接返回false
        {
            cout<<k-1<<endl;
            for(int i=0;i<k;i++)
            {
                cout<<x[i]<<" ";
            }
            return 0;
        }
    }
    return 0;
}

完结撒花🎉~