• 算法分析与设计编程题 回溯法

    装载问题

    题目描述

    在这里插入图片描述

    解题代码

    递归回溯

    // 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;
}

    • 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

    状态压缩

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

    由于递归回溯的本质可以看作是对一棵二叉树进行的搜索，每次选或者不选都将产生两个分支，那么所有情况的数量为 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).

    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

    符号三角形问题

    题目描述

    在这里插入图片描述

    解题代码

    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;
}

    • 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

    N皇后

    题目描述

    在这里插入图片描述

    解题代码

    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

    最大团问题

    题目描述

    在这里插入图片描述

    解题代码

    // 图的邻接矩阵形式
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;
}

    • 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

    图的m着色问题

    题目描述

    在这里插入图片描述

    解题代码

    // 图的邻接矩阵形式
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

    圆排列问题

    题目描述

    在这里插入图片描述

    解题代码

    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;
}

    • 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
  • 相关阅读:
    新手学习 python 的好工具：PyScripter
    cmake练习一
    入侵特斯拉的方式 +1，而这次……似乎仅需一部手机？
    华为云GaussDB(for Redis)支撑数位科技打造全新大数据引擎
    OpenAI再次与Altman谈判；ChatGPT Voice正式上线
    can的波特率/比特率
    【批处理DOS-CMD命令-汇总和小结】-跳转、循环、条件命令（goto、errorlevel、if、for[读取、切分、提取字符串]、）cmd命令错误汇总
    计算机毕业设计（附源码）python重工教师职称管理系统
    k8s-15 strogeclass
    SpringBoot中一个万能的Cors跨域Filter
  • 原文地址：https://blog.csdn.net/qq_37409526/article/details/132891855