装载问题

题目描述

解题代码

递归回溯

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
// goods[i]表示货物i的重量, c1,c2分别表示货船1和货船2的载重量
vector<vector<int>> optimalLoading(vector<int>& goods, int c1, int c2) {
	int n = goods.size(); // 货物数量
	int maxSum = 0; // 当前最大载货量
	// curSelection[i]表示货物i是否放入货船1中（true表示放入）
	vector<bool> curSelection(n, false);
	// optimSelection记录maxSum对应的货物存放方式
	vector<bool> optimSelection;

	// 递归搜索函数
	function<void(int, int)> dfs = [&](int sum, int idx) {
		if (idx == n) { // 搜索达到最大深度，得到一个解
			if (sum > maxSum) { // 更新最优解
				maxSum = sum;
				optimSelection = curSelection;
			}
			return;
		}
		// 货物idx能否放入货船1，若能，则向下搜索
		if (sum + goods[idx] <= c1) {
			curSelection[idx] = true;
			dfs(sum + goods[idx], idx + 1);
			curSelection[idx] = false;
		}
		// 不考虑将货物idx放入货船1
		dfs(sum, idx + 1);
	};

	dfs(0, 0); // 执行搜索，初始时sum和idx均为0

	// 判断在最优解情况下（将尽可能重的货物放入货船1后），余下的货物能否放入货船2
	int sum2 = 0;
	for (int i = 0; i < n; ++i) {
		if (!optimSelection[i]) {
			sum2 += goods[i];
		}
	}
	if (sum2 > c2) return {}; // 若不能，则此问题无解，返回空数组
	// 若能，则构造最优解
	vector<vector<int>> res(2);
	for (int i = 0; i < n; ++i) {
		if (optimSelection[i]) { // 选择放入货船1
			res[0].emplace_back(goods[i]);
		}
		else { // 选择放入货船2
			res[1].emplace_back(goods[i]);
		}
	}
	return res;
}

状态压缩

事实上，对于此类涉及选或不选的回溯算法，还可以将其写成迭代的形式。

由于递归回溯的本质可以看作是对一棵二叉树进行的搜索，每次选或者不选都将产生两个分支，那么所有情况的数量为 2n（n 为被搜索对象的数目，在本例中为货物的总数）。我们考虑用一个整数 mask 将每种情况表示出来，该整数称为掩码，关注它的 n 位二进制形式，其中 mask 的第 i 位二进制位就代表对应的货物 goods[i] 有没有被选择，通常用 1 代表被选择，0 代表不被选择。那么不难得知 mask 的范围为 0~2n-1 。

在得到了每一种情况下的掩码后，就需要对其进行解码了，可以遍历 0~n-1 的所有整数 i，并将其右移 i 位，将 goods[i] 的对应的二进制位移到了最低位，此时再将和 1 进行按位与运算就能得知此情况下货物 i 是否被选择。

两种算法都有 2n 中搜索状态，每种状态下需要 O(n) 时间来进行最优解的更新，因此两种算法的渐进时间复杂度都为 O(n * 2n).

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
vector<vector<int>> optimalLoading(vector<int>& goods, int c1, int c2) {
	int n = goods.size();
	vector<bool> curSelection(n, false);
	vector<bool> optimSelection;
	int maxSum = 0;
	for (int mask = 0; mask < (1 << n); ++mask) { // 遍历每种情况
		// 将sum和curSelection全部复位
		int sum = 0;
		curSelection.assign(n, false);
		for (int i = 0; i < n; ++i) {
			bool isChoosed = (mask >> i) & 1;
			if (!isChoosed) continue;
			if (sum + goods[i] <= c1) {
				sum += goods[i];
				curSelection[i] = true;
			}
		}
		if (sum > maxSum) {
			maxSum = sum;
			optimSelection = curSelection;
		}
	}

	// 构造最优解（与递归回溯部分完全相同）
	int sum2 = 0;
	for (int i = 0; i < n; ++i) {
		if (!optimSelection[i]) {
			sum2 += goods[i];
		}
	}
	if (sum2 > c2) return {};
	vector<vector<int>> res(2);
	for (int i = 0; i < n; ++i) {
		if (optimSelection[i]) {
			res[0].emplace_back(goods[i]);
		}
		else {
			res[1].emplace_back(goods[i]);
		}
	}
	return res;
}

批处理作业调度

题目描述

解题代码

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
int batchJobScheduling(vector<vector<int>>& jobs) {
	int n = jobs.size(); // 作业数量
	int res = INT32_MAX, curSum = 0; // 最优调度时间，当前调度时间
	int f1 = 0; // 机器1完成处理时间
	vector<int> f2(n + 1, 0); // 机器2完成处理时间
	vector<int> optimSche; // 最优调度方案
	vector<int> curSche; // 当前调度方案
	for (int i = 0; i < n; ++i) { // 初始调度方案为 0,1,2,...,n-1
		curSche.emplace_back(i);
	}

	// 递归搜索函数
	function<void(int)> dfs = [&](int idx) {
		if (idx == n) { // 搜索达到最大深度
			// 更新最优解
			optimSche = curSche;
			res = curSum;
			return;
		}
		for (int j = idx; j < n; ++j) { // 全排列搜索
			f1 += jobs[curSche[j]][0];
			f2[idx + 1] = ((f2[idx] > f1) ? f2[idx] : f1) + jobs[curSche[j]][1];
			curSum += f2[idx + 1];
			if (curSum < res) { // 剪枝（若当前累计和已经大于等于最优解，则不继续向下搜索）
				swap(curSche[idx], curSche[j]);
				dfs(idx + 1);
				swap(curSche[idx], curSche[j]);
			}
			// 回溯
			f1 -= jobs[curSche[j]][0];
			curSum -= f2[idx + 1];
		}
	};

	dfs(0); // 递归搜索
	// 打印最优调度方案
	for (int i = 0; i < n; ++i) {
		cout << optimSche[i];
		if (i < n - 1) cout << "->";
	}
	return res;
}

符号三角形问题

题目描述

解题代码

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
int signedTriangle(int n) {
	int num = n * (n + 1) / 2; // 三角形符号总数
	if (num % 2 == 1) return 0; // 总数为奇数，不可能相等
	vector<bool> triangles(num, false); // false代表'+',true代表'-'
	int res = 0; // 合法图形个数
	vector<vector<bool>> fullShape; // 所有合法图形

	// 递归搜索函数
	function<void(int)> dfs = [&](int idx) {
		if (idx == n) { // 到达最大搜索深度，判断是否可行
			int pCnt = num / 2, sCnt = num / 2; // 剩余'+','-'的符号个数
			vector<bool> newShape; // 当前图形
			queue<bool> q, nq; // 轮换队列
			for (int i = 0; i < n; ++i) { // 将第一行符号加入队列
				q.emplace(triangles[i]);
				newShape.emplace_back(triangles[i]);
				--(triangles[i] ? sCnt : pCnt);
			}
			while (q.size() > 1) {
				while (q.size() > 1) {
					bool ft = q.front();
					q.pop();
					bool nt = ft ^ q.front(); // 队列前两个符号异或得到下面的符号
					nq.emplace(nt);
					--(nt ? sCnt : pCnt);
					if (sCnt * pCnt < 0) return; // 其中一个符号个数超过一半
					newShape.emplace_back(nt);
				}
				q = move(nq); // 队列轮换（利用右值引用进行资源所有权的交换）
			}
			// 该结果合法
			++res;
			fullShape.emplace_back(newShape);
			return;
		}
		triangles[idx] = true;
		dfs(idx + 1);
		triangles[idx] = false;
		dfs(idx + 1);
	};

	dfs(0); // 递归搜索
	// 打印所有合法图形
	for (const auto& shape : fullShape) {
		for (int col = n; col >= 1; --col) {
			int di = (n - col) * (n + col + 1) / 2;
			for (int i = 0; i < col; ++i) {
				cout << shape[i + di];
			}
			cout << endl;
		}
		cout << "\n" << endl;
	}
	return res;
}

N皇后

题目描述

解题代码

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
vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res; // 存放所有解
    vector<string> chessBoard(n, string(n, '.')); // 当前棋盘状态

    // 检查该位置(r,c)是否能够放置棋子
    auto check = [&](int r, int c) -> bool {
        for (int i = 0; i < r; ++i) {
            // 从上往下依次检查棋盘第c列是否已放置棋子
            if (chessBoard[i][c] == 'Q') {
                return false;
            }
            // 从下往上依次检查左斜上方是否已放置棋子
            int li = r - i - 1, lj = c - i - 1;
            if (li >= 0 && lj >= 0 && chessBoard[li][lj] == 'Q') {
                return false;
            }
            // 从下往上依次检查右斜上方是否已放置棋子
            int ri = r - i - 1, rj = c + i + 1;
            if (ri >= 0 && rj < n && chessBoard[ri][rj] == 'Q') {
                return false;
            }
        }
        return true;
    };

    // 递归搜索函数
    function<void(int)> dfs = [&](int idx) {
        if (idx == n) { // 到达最大深度，得到一个合法解
            res.emplace_back(chessBoard);
            return;
        }
        for (int j = 0; j < n; ++j) {
            if (!check(idx, j)) continue; // 当前位置不可放置
            chessBoard[idx][j] = 'Q'; // 放置棋子
            dfs(idx + 1);
            chessBoard[idx][j] = '.'; // 回溯
        }
    };

    dfs(0);
    return res;
}

最大团问题

题目描述

解题代码

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
// 图的邻接矩阵形式
struct MGraph {
	vector<char> vertices; // 顶点数组（元素为字符类型）
	// 邻接矩阵，edges[u][v] == INT32_MAX ? 无边 : 存在权值为edges[u][v]的边
	vector<vector<int>> edges;
};

vector<vector<char>> largestGroup(MGraph& G) {
	int n = G.vertices.size(); // 顶点个数
	 // 所有的最大团（每个最大团为一个char类型数组，其中元素为最大团顶点）
	vector<vector<char>> res;
	vector<bool> curGroup(n, false); // 当前团
	int maxSize = 0; // 团的最大顶点数

	// 递归搜索函数，idx为搜索深度，curSize为当前搜索状态下团的顶点个数
	function<void(int, int)> dfs = [&](int idx, int curSize) {
		if (idx == n) { // 到达最大搜索深度
			// 构造最大团
			vector<char> group;
			for (int i = 0; i < n; ++i) {
				if (curGroup[i]) {
					group.emplace_back(G.vertices[i]);
				}
			}
			// 更新最优解
			if (curSize > maxSize) {
				res.clear();
				maxSize = curSize;
			}
			res.emplace_back(group);
			return;
		}
		bool flag = true; // 判断当前结点idx是否能够与当前团的每个结点相连
		for (int j = 0; j < idx; ++j) {
			if (curGroup[j] && G.edges[idx][j] == INT32_MAX) {
				flag = false;
				break;
			}
		}
		if (flag) { // 如果相连，则构成一个更大的团，继续向下搜索
			curGroup[idx] = true; // 加入团
			dfs(idx + 1, curSize + 1);
			curGroup[idx] = false; // 回溯
		}
		// 剪枝，若满足curSize + n - idx <= maxSize
		// 则不可能得到比当前最大团更大的团，无需继续搜索
		if (curSize + n - idx > maxSize) {
			dfs(idx + 1, curSize);
		}
	};

	dfs(0, 0);
	return res;
}

图的m着色问题

题目描述

解题代码

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
// 图的邻接矩阵形式
struct MGraph {
	vector<char> vertices; // 顶点数组（元素为字符类型）
	// 邻接矩阵，edges[u][v] == INT32_MAX ? 无边 : 存在权值为edges[u][v]的边
	vector<vector<int>> edges;
};

vector<vector<int>> mColoring(MGraph& G, int m) {
	int n = G.vertices.size(); // 图的顶点个数
	vector<vector<int>> res; // 所有着色方案，若无合法着色方案，则为空
	vector<int> coloring(n, -1); // 当前着色方案

	// 检查所有与顶点idx相连的顶点j是否与顶点idx颜色相同，若相同，则此着色方案不合法
	auto check = [&](int idx) -> bool {
		for (int j = 0; j < n; ++j) {
			if (G.edges[idx][j] != INT32_MAX && coloring[idx] == coloring[j]) {
				return false;
			}
		}
		return true;
	};

	// 递归搜索函数
	function<void(int)> dfs = [&](int idx) {
		if (idx == n) { // 到达最大搜索深度，将该着色方案加入解集中
			res.emplace_back(coloring);
			return;
		}
		// 遍历所有颜色，尝试为顶点idx进行着色
		for (int j = 0; j < m; ++j) {
			coloring[idx] = j; // 着色
			if (check(idx)) { // 此着色合法，继续向下搜索
				dfs(idx + 1);
			}
			coloring[idx] = -1; // 回溯
		}
	};

	dfs(0);
	return res;
}

圆排列问题

题目描述

解题代码

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
double circlePermutation(vector<double>& radius) {
	int n = radius.size(); // 圆的个数
	double res = INT32_MAX; // 最小长度
	vector<double> optimalPerm; // 最小长度对应的排列方式
	vector<double> curX(n); // curX[i]表示当前排列下圆i的圆心横坐标

	// 计算当前排列下圆idx的圆心横坐标
	auto calCenter = [&](int idx) -> double {
		double xMax = 0.0;
		for (int j = 0; j < idx; ++j) {
			double x = curX[j] + 2.0 * sqrt(radius[idx] * radius[j]);
			xMax = max(xMax, x);
		}
		return xMax;
	};

	// 计算当前排列下的总长度
	auto calLen = [&]() -> double {
		double low = 0.0, high = 0.0;
		for (int i = 0; i < n; ++i) {
			low = min(low, curX[i] - radius[i]);
			high = max(low, curX[i] + radius[i]);
		}
		return high - low;
	};

	// 递归搜索函数
	function<void(int)> dfs = [&](int idx) {
		if (idx == n) { // 到达最大搜索深度
			double len = calLen();
			if (len < res) { // 更新最优解
				res = len;
				optimalPerm = radius;
			}
		}
		for (int j = idx; j < n; ++j) { // 全排列
			swap(radius[idx], radius[j]);
			double centerX = calCenter(idx);
			if (centerX + radius[idx] + radius[0] < res) { // 剪枝
				curX[idx] = centerX;
				dfs(idx + 1);
			}
			swap(radius[idx], radius[j]);
		}
	};

	dfs(0);
	// 打印最优解对应的圆排列
	for (int i = 0; i < n; ++i) {
		cout << optimalPerm[i] << " ";
	}
	return res;
}