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

装载问题

题目描述

在这里插入图片描述

解题代码

递归回溯

// 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放入货船1dfs(sum, idx + 1);};dfs(0, 0); // 执行搜索，初始时sum和idx均为0// 判断在最优解情况下（将尽可能重的货物放入货船1后），余下的货物能否放入货船2int 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]) { // 选择放入货船1res[0].emplace_back(goods[i]);}else { // 选择放入货船2res[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).

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

批处理作业调度

题目描述

在这里插入图片描述

解题代码

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-1curSche.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;
}

符号三角形问题

题目描述

在这里插入图片描述

解题代码

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皇后

题目描述

在这里插入图片描述

解题代码

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

最大团问题

题目描述

在这里插入图片描述

解题代码

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

题目描述

在这里插入图片描述

解题代码

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

圆排列问题

题目描述

在这里插入图片描述

解题代码

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/132438.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

新知同享 | Web 开发性能提升，优化体验

新知同享 | Web 开发性能提升，优化体验

更加强大且开放的 Web 可以简化开发工作并支持 AI 一起来看 2023 Google 开发者大会上 Web 开发值得重点关注的升级与成果 了解 Web 如何实现加速开发&#xff0c;更加便捷 精彩大会现场一览 Web 开发不断发展&#xff0c;每年都带来性能提升和功能迭代&#xff0c;开启丰富多…
阅读更多...
【C++】常用算术生成算法

【C++】常用算术生成算法

0.前言 1.accumulate #include <iostream> using namespace std;// 常用算术生成算法 #include<vector> #include<numeric> //accumulate 的调用头文件void test01() {vector<int>v;for (int i 0; i < 100; i){v.push_back(i);}int total accumu…
阅读更多...
Mysql InnoDB引擎 的hash索引

Mysql InnoDB引擎 的hash索引

Mysql InnoDB引擎不支持hash索引&#xff0c;但是在内存结构中有一个自适应hash索引&#xff0c;来提高查询性能 当设置hash索引时会自动转换成btree索引 查一下mysql官方文档&#xff1a;https://dev.mysql.com/doc/refman/5.7/en/create-index.html innodb_adaptive_hash_i…
阅读更多...
数据在内存中的存储

数据在内存中的存储

目录 数据类型 大小端 判断大小端 练习 1 2 浮点数在内存中储存 存M 存E 取E 数据类型 整形家族&#xff1a; char unsigned char signed char short unsigned short [int] signed short [int] int unsigned int signed int long unsigned long [int] signed…
阅读更多...
Day_14 ＞ 指针进阶（3）＞ bubble函数

Day_14 ＞ 指针进阶（3）＞ bubble函数

目录 1.回顾回调函数 2.写一个bubble_sort函数 2.1认识一下qsort函数 ​编辑2.2写bubble_sort函数 今天我们继续深入学习指针 1.回顾回调函数 我们回顾一下之前学过的回调函数 回调函数就是一个通过函数指针调用的函数 如果你把函数的指针&#xff08;地址&#xff09;…
阅读更多...
数据可视化大屏模板 | 保姆级使用教程

数据可视化大屏模板 | 保姆级使用教程

近来很多朋友私信咨询怎么下载使用数据可视化大屏模板&#xff0c;在这里就给大家做一个相对简单的教程总结。有需要的朋友记得先收藏保存&#xff0c;以便不时之需。 数据可视化大屏制作软件&#xff1a;奥威BI系统 数据可视化报表模板板块&#xff1a;模板秀 主要操作&…
阅读更多...
Unity下如何实现RTMP或RTSP播放端录像？

Unity下如何实现RTMP或RTSP播放端录像？

好多开发者问我们&#xff0c;Unity环境下&#xff0c;除了RTSP或RTMP的播放&#xff0c;如果有录像诉求&#xff0c;怎么实现&#xff1f;实际上录像相对播放来说&#xff0c;更简单一些&#xff0c;因为不涉及到绘制&#xff0c;只要拉流下来数据&#xff0c;直接写mp4文件就…
阅读更多...
【数据结构】二叉树的链式结构

【数据结构】二叉树的链式结构

【数据结构】二叉树的链式存储结构 二叉树的存储结构 typedef int BTDataType; // 二叉树的结构 typedef struct BinaryTreeNode {BTDataType data; // 树的值struct BinaryTreeNode *left; // 左孩子struct BinaryTreeNode *right;// 右孩子 } BinaryTreeNode;二…
阅读更多...
跟模型和中间层聊聊：什么是最好的AI原生应用？

跟模型和中间层聊聊：什么是最好的AI原生应用？

软件 2.0 注定会发生&#xff1a;所有软件都值得用神经网络重做一遍。 这个 OpenAI 大神 Karpathy 多年前的预言&#xff0c;指向了今天 LLM 应用层的一个关键问题——如何基于 LLM 能力&#xff0c;设计好 AI 原生应用。 我们看到&#xff0c;应用层的创业者们感到悲观、质疑和…
阅读更多...
腾讯发布超千亿参数规模的混元大模型；深度学习与音乐分析与生成课程介绍

腾讯发布超千亿参数规模的混元大模型；深度学习与音乐分析与生成课程介绍

&#x1f989; AI新闻 &#x1f680; 腾讯发布超千亿参数规模的混元大模型 摘要&#xff1a;腾讯在2023腾讯全球数字生态大会上发布混元大模型&#xff0c;该模型拥有超千亿的参数规模和超2万亿 tokens 的预训练语料。混元大模型将支持多轮对话、内容创作、逻辑推理、知识增强…
阅读更多...
计算机毕设 大数据上海租房数据爬取与分析可视化 -python 数据分析 可视化

计算机毕设 大数据上海租房数据爬取与分析可视化 -python 数据分析 可视化

# 1 前言 &#x1f525; 这两年开始毕业设计和毕业答辩的要求和难度不断提升&#xff0c;传统的毕设题目缺少创新和亮点&#xff0c;往往达不到毕业答辩的要求&#xff0c;这两年不断有学弟学妹告诉学长自己做的项目系统达不到老师的要求。 为了大家能够顺利以及最少的精力通…
阅读更多...
Zookeeper应用场景和底层设计

Zookeeper应用场景和底层设计

一、什么是zookeeper Zookeeper是一个开源的分布式协调服务框架&#xff0c;它是服务于其它集群式框架的框架。 【简言之】 有一个服务A&#xff0c;以集群的方式提供服务。只需要A专注于它提供的服务就可以&#xff0c;至于它如何以多台服务器协同完成任务的事情&#xff0c…
阅读更多...
(文末赠书)我为什么推荐应该人手一本《人月神话》

(文末赠书)我为什么推荐应该人手一本《人月神话》

能点进来的朋友&#xff0c;说明你肯定是计算机工作的朋友或者对这本书正在仔细琢磨着的朋友。 文章目录 1、人人都会编程的时代&#xff0c;我们如何留存?2、小故事说明项目管理着为什么必看这本书3、如何评价《人月神话&#xff1a;纪念典藏版》4、本书的目录&#xff08;好…
阅读更多...
科技资讯|苹果Vision Pro获得被动冷却系统及数字表冠控制界面专利

科技资讯|苹果Vision Pro获得被动冷却系统及数字表冠控制界面专利

据patentlyapple报道&#xff0c;美国专利商标局正式授予苹果一项与头戴式设备&#xff08;Apple Vision Pro&#xff09;相关的专利11751366&#xff0c;该设备可以提供被动冷却系统&#xff0c;利用光学组件的表面来管理热量&#xff0c;而不会对用户显示的视觉信息产生不利影…
阅读更多...
博客系统（升级（Spring））(四)（完）基本功能（阅读，修改，添加，删除文章）（附带项目）

博客系统（升级（Spring））(四)（完）基本功能（阅读，修改，添加，删除文章）（附带项目）

博客系统 (三&#xff09; 博客系统博客主页前端后端个人博客前端后端显示个人文章删除文章 修改文章前端后端提取文章修改文章 显示正文内容前端后端文章阅读量功能 添加文章前端后端 如何使用Redis项目地点&#xff1a; 博客系统 博客系统是干什么的&#xff1f; CSDN就是一…
阅读更多...
【用unity实现100个游戏之10】复刻经典俄罗斯方块游戏

【用unity实现100个游戏之10】复刻经典俄罗斯方块游戏

文章目录 前言开始项目网格生成Block方块脚本俄罗斯方块基类&#xff0c;绘制方块形状移动逻辑限制移动自由下落下落后设置对应风格为不可移动类型检查当前方块是否可以向指定方向移动旋转逻辑消除逻辑游戏结束逻辑怪物生成源码参考完结 前言 当今游戏产业中&#xff0c;经典游…
阅读更多...
关于HTTP协议的概述

关于HTTP协议的概述

HTTP 的报文大概分为三大部分。第一部分是请求行&#xff0c;第二部分是请求的首部&#xff0c;第三部分才是请求的正文实体。 POST 往往是用来创建一个资源的&#xff0c;而 PUT 往往是用来修改一个资源的。 Accept-Charset&#xff0c;表示客户端可以接受的字符集。防止传过…
阅读更多...
YOLOv5：修改backbone为ConvNeXt

YOLOv5：修改backbone为ConvNeXt

YOLOv5&#xff1a;修改backbone为ConvNeXt 前言前提条件相关介绍ConvNeXtYOLOv5修改backbone为ConvNeXt修改common.py修改yolo.py修改yolov5.yaml配置 参考 前言 记录在YOLOv5修改backbone操作&#xff0c;方便自己查阅。由于本人水平有限&#xff0c;难免出现错漏&#xff0c…
阅读更多...
python 列表常用方法

python 列表常用方法

python的列表和js的数组是相似的 mylist ["add", "item", "msg", "add", "add", "add"] # 语句[索引] 值 改变列表中某一项的值 # mylist[1] 122 # insert插入值 # mylist.insert(2, "age") # appe…
阅读更多...
Vite和Webpack如何使用CDN包

Vite和Webpack如何使用CDN包

为了精简打包输出的dist目录大小&#xff0c;我们可以引入CDN外部包的方式&#xff0c;来缩小打包的体积&#xff0c;加快打包速度。这里介绍Vite和Webpack中如何引入React CDN外部包。 一、Vite引入CDN包 1、安装插件 npm i vitejs/plugin-react-refresh vite-plugin-cdn-i…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023