课程网站资源建设小结,哪个网站做外贸生意,杭州建设网杭州建设工程招标平台,做自己的网站收费吗第五次作业【回溯算法】 文章目录 第五次作业【回溯算法】1 算法分析题5-3 回溯法重写0-1背包2 算法分析题5-5 旅行商问题#xff08;剪枝#xff09;3 算法实现题5-2 最小长度电路板排列问题4 算法实现题5-7 n色方柱问题5 算法实现…第五次作业【回溯算法】 文章目录 第五次作业【回溯算法】1 算法分析题5-3 回溯法重写0-1背包2 算法分析题5-5 旅行商问题剪枝3 算法实现题5-2 最小长度电路板排列问题4 算法实现题5-7 n色方柱问题5 算法实现题5-13 任务分配问题 1 算法分析题5-3 回溯法重写0-1背包
▲问题重述
一共有N件物品第ii从0开始件物品的重量为weight[i]价值为value[i]。在总重量不超过背包承载上限maxw的情况下求能够装入背包的最大价值是多少并要求输出选取的物品编号。
要求使用回溯法求解
▲解题思路
使用回溯法。构造解空间树从第0层到第n-1层每层表示对于背包内某个物品的“取”或“不取”。第n层为答案层在第n层进行判定结果是否是想要的即能不能获得更优的解若是就做出相应的处理。
这是一个万能的解空间树图借来用用。 剪枝想法
1如果在第n层之前就出现了总和大于的maxw情况那么此时已经超重了。之后无论是否取都不可能再得到总和小于maxw的结果了。这种情况以及它的子树直接删去即可。
2如果在第n层之前目前已有的价值即使加上剩余可取的最大价值也不能达到已经达到的bestv那么之后即使全部取也不能达到bestv了。这种情况及它的子树直接删去即可。
剪枝代码可以删去不影响结果但会降低效率。
▲代码
// -*- coding:utf-8 -*-// File : 01背包问题回溯.cpp
// Time : 2023/12/14
// Author : wolf#include iostream
using namespace std;int w[5000];
int v[5000];
bool flag[5000];
bool ans[5000];
int now_w 0, now_v 0;
int n, maxw, bestv 0;
int rest_v;void backtrace(int depth)
{if (depth n) // 到达第n层答案{if (now_v bestv now_w maxw) // 答案是需要打印的{bestv now_v;for (int i 0; i n; i){ans[i] flag[i];}}return;}if (depth n now_w maxw)return; // 剪枝此时背包已经过重if (now_v rest_v bestv)return; // 剪枝此时剩余价值即使全部拾取也无法达到最大价值rest_v - v[depth];// 取这个物品now_v v[depth];now_w w[depth];flag[depth] 1;backtrace(depth 1);now_v - v[depth];now_w - w[depth];flag[depth] 0;// 不取这个物品backtrace(depth 1);rest_v v[depth];return;
}int main()
{cin maxw n;for (int i 0; i n; i){cin w[i] v[i];ans[i] 0;flag[i] 0;rest_v v[i];}backtrace(0);for (int i 0; i n; i){if (ans[i])cout i ;}cout endl;cout bestv endl;return 0;
}
▲验证
洛谷P1048https://www.luogu.com.cn/problem/P1048
【验证时把输出最优解向量的for循环删去题目要求不一样】 回溯法解决背包问题的O(2n)还是从数量级上显著不如动态规划的O(n2)。
故在数据量很大的时候不能通过测评显示超时。
所以01背包问题还是得用动态规划解本题只是练习一下回溯法。
2 算法分析题5-5 旅行商问题剪枝
▲题目重述 ▲解答 ▲代码
// -*- coding:utf-8 -*-// File : 5-5 旅行售货员问题.cpp
// Time : 2023/12/30
// Author : wolf#include iostreamusing namespace std;
int const MAXINT 99999;
int map[1000][1000];
int v, e, best_cost MAXINT, now_cost 0;
int now_order[1000]; // 储存当前排列解向量
int ans[1000]; // 储存结果排列解向量
int upbound;void swap(int a, int b)
{int temp now_order[a];now_order[a] now_order[b];now_order[b] temp;
};void backtrack(int depth)
{if (depth v - 1) // 到达答案层{if (map[now_order[depth]][now_order[0]] ! -1) // 能跟第一个相连{now_cost map[now_order[depth]][now_order[0]];if (now_cost best_cost) // 更优保存结果{best_cost now_cost;for (int i 0; i v; i){ans[i] now_order[i];}}now_cost - map[now_order[depth]][now_order[0]];}}else{for (int i depth; i v; i) // 生成排列树当前向量中depth位置的节点编号第depth个访问哪个节点{if (map[now_order[depth - 1]][now_order[i]] ! -1) // 前一节点到当前的这个节点有可达边{if (now_cost map[now_order[depth - 1]][now_order[i]] upbound)// 剪枝若当前步骤使得费用和就大于上界了不必继续{swap(i, depth);now_cost map[now_order[depth - 1]][now_order[depth]];backtrack(depth 1);now_cost - map[now_order[depth - 1]][now_order[depth]];swap(i, depth);}}}}return;
}
int main()
{cin v e;for (int i 0; i v; i)for (int j 0; j v; j)map[i][j] -1;for (int i 0; i e; i){int a, b, weight;cin a b weight;map[a][b] weight;map[b][a] weight;}// 剪枝预备for (int i 0; i v; i){int i_out_max 0; // 存储从i节点向外for (int j 0; j v; j){i_out_max max(i_out_max, map[i][j]);}upbound i_out_max;}// 指定从0号节点开始遍历// 反正最后每一个节点都需要遍历过for (int i 0; i v; i)now_order[i] i; // 初始按照递增顺序初始顺序是无所谓的只要保证都能遍历一遍就可以backtrack(1); // 0号节点已固定搜索从1号节点开始的全排列cout best_cost endl;return 0;
}
▲验证
input
4 5
0 1 10
0 2 15
1 2 35
1 3 25
2 3 30output
503 算法实现题5-2 最小长度电路板排列问题
▲问题重述 ▲解题思路
排列树解决问题。创建以下函数/类
Board 类: class Board 定义了一个名为 Board 的类用于处理电路板排列问题。私有成员变量包括 n电路板数、m连接块数、x当前解的数组、bestx当前最优解的数组、bestd当前最优密度、low辅助数组存储连接块的最小高度、high辅助数组存储连接块的最大高度、B连接块数组。 len 函数: int len(int ii) 用于计算排列中的某一部分的长度即连接块之间的最大高度差。该函数首先将 low 和 high 数组初始化为合适的值然后根据当前排列计算连接块的最小和最大高度最后计算最大高度差并返回。 Backtrack 函数: void Backtrack(int i) 是一个递归函数用于在排列树上进行回溯搜索寻找最优解。当达到排列树的终点i n时计算当前排列的长度并更新最优解。否则对于当前位置 i尝试选择不同的电路板进行交换然后继续递归搜索。 ArrangeBoards 函数: int ArrangeBoards(int **B, int n, int m, int *bestx) 是主要的调用函数。在该函数中创建一个 Board 类的实例 X并通过初始化设置其成员变量。利用回溯算法调用 Backtrack(1) 来找到最优解。返回最优解的密度。 main 函数: main 函数读取输入调用 ArrangeBoards 函数来解决问题并输出结果。动态分配二维数组 B 以存储连接块信息。读取输入的电路板连接信息。创建数组 bestx 用于存储最优解。输出最优解的密度和排列。
▲代码
// 电路板排列问题
#include bits/stdc.h
using namespace std;
class Board
{friend int ArrangeBoards(int **, int, int, int *);private:void Backtrack(int i);int len(int ii);int n, // 电路板数m, // 连接块数*x, // 当前解*bestx, // 当前最优解bestd, // 当前最优密度*low, //*high, //**B; // 连接块数组
};
int Board::len(int ii)
{for (int i 0; i m; i){high[i] 0;low[i] n 1;}for (int i 1; i ii; i){for (int k 1; k m; k){if (B[x[i]][k]){if (i low[k])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])tmp high[k] - low[k];}return tmp;
}
void Board::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];}}else{for (int j i; j n; j) // 选择x[j]为下一块电路板{swap(x[i], x[j]);int ld len(i);if (ld bestd)Backtrack(i 1);swap(x[i], x[j]);}}
}
int ArrangeBoards(int **B, int n, int m, int *bestx)
{Board X;// 初始化XX.x new int[n 1];X.low new int[m 1];X.high new int[m 1];X.B B;X.n n;X.m m;X.bestx bestx;X.bestd n 1;// 初始化total和nowfor (int i 1; i n; i){X.x[i] i;}X.Backtrack(1);delete[] X.x;delete[] X.low;delete[] X.high;return X.bestd;
}
int main()
{int n, m;cin n m;int **B new int *[n 1];for (int i 0; i n; i)B[i] new int[m 1];for (int i 1; i n; i)for (int j 1; j m; j)cin B[i][j];int *bestx new int[n 1];for (int i 1; i n; i)bestx[i] 0;int ans ArrangeBoards(B, n, m, bestx);cout ans endl;for (int i 1; i n; i)cout bestx[i] ;cout endl;return 0;
}
▲验证
测试案例
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测试结果 4 算法实现题5-7 n色方柱问题
▲问题重述
设有 n 个立方体每个立方体的每一面用红、黄、蓝、绿等 n 种颜色之一染色。要把这n 个立方体叠成一个方形柱体使得柱体的 4 个侧面的每一侧均有 n 种不同的颜色。试设计一个回溯算法计算出 n 个立方体的一种满足要求的叠置方案。
对于给定的 n 个立方体以及每个立方体各面的颜色计算出 n 个立方体的一种叠置方案使得柱体的 4 个侧面的每一侧均有 n 种不同的颜色。
数据输入
第一行有 1 个正整数 n0 n 27表示给定的立方体个 数和颜色数均为 n。第 2 行是 n 个大写英文字母组成的字符串。该字符串的第 k(0≤ k n) 个字符代表第 k 种颜色。接下来的 n 行中每行有 6 个数表示立方体各面的颜色。立方体各面的编号如下图所示。 图中 F 表示前面B 表示背面L 表示左面R 表示右面T 表示顶面D 表示底面。相 应地2 表示前面3 表示背面0 表示左面1 表示右面5 表示顶面4 表示底面。 例如在示例输出文件中第3行的6个数0 2 1 3 0 0分别表示第1个立方体的左面的颜色为R, 右面的颜色为B, 前面的颜色为G, 背面的颜色为Y, 底面的颜色为R, 顶面的颜色为 R。
案例
input
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 output
RBGYRR
YRBGRG
BGRBGY
GYYRBB▲解题思路
在下面的代码中使用注释讲解。使用回溯法的思路套用回溯法的模板但有改动。
本题比较晦涩难懂在理解上需要花很多时间。
关于代码部分的映射方式 ▲代码
// -*- coding:utf-8 -*-// File : 5-7 n色方柱问题.cpp
// Time : 2023/12/27
// Author : wolf#include iostreamusing namespace std;
char color[28]; // 用来储存输入的数字对应的颜色只在输出的时候转换为字符在做题时使用数字存储
int box[28][6]; // box[i][j]用来储存第i个立方体各个面即第j面的颜色
int n;
int count 1; // 标记这是第几个输出的可能结果
const int place[24][6] {// 转动立方体的映射函数使用box[depth1][j]origin[place[method][j]]来获取第method种方法下下一层的摆放方式// place[i][j]为第i种转换方法下该立方体该层的第j面应该变换为place[i][j]{0, 1, 2, 3, 4, 5},{4, 5, 2, 3, 1, 0},{1, 0, 2, 3, 5, 4},{5, 4, 2, 3, 0, 1}, // 2为底面3为顶面{0, 1, 3, 2, 4, 5},{4, 5, 3, 2, 1, 0},{1, 0, 3, 2, 5, 4},{5, 4, 3, 2, 0, 1}, // 3为底面2为顶面{3, 2, 0, 1, 4, 5},{4, 5, 0, 1, 2, 3},{2, 3, 0, 1, 5, 4},{5, 4, 0, 1, 3, 2}, // 0为底面1为顶面{3, 2, 1, 0, 4, 5},{4, 5, 1, 0, 2, 3},{2, 3, 1, 0, 5, 4},{5, 4, 1, 0, 3, 2}, // 1为底面0为顶面{1, 0, 4, 5, 3, 2},{3, 2, 4, 5, 0, 1},{0, 1, 4, 5, 2, 3},{2, 3, 4, 5, 1, 0}, // 4为底面5为顶面{1, 0, 5, 4, 3, 2},{3, 2, 5, 4, 0, 1},{0, 1, 5, 4, 2, 3},{2, 3, 5, 4, 1, 0}, // 5为底面4为顶面
};void backtrack(int depth)
{// cout depth depth endl;if (depth n - 1) // 到达答案层{cout Possible Solution count : endl;count;for (int i 0; i n; i){for (int j 0; j 6; j){cout color[box[i][j]] ;}cout endl;}cout endl;}else{int process depth 1;int origin[6];// 【使用origin[]数组先保存原始情况可以省去整体恢复原状的步骤24次for循环每次都是新的开始】for (int i 0; i 6; i) // 保存待处理层初始存放的颜色origin[i] box[process][i]; // origin[i]表示该层初始第i个面存放的颜色// cout origin endl;// for (int i 0; i 6; i)// cout origin[i] ;// cout endl;for (int i 0; i 24; i) // 列举子集树每个立方体有24种放法,第i种方法{// cout method i endl;for (int j 0; j 6; j) // 按照该种方案的映射把处理的该层立方体先摆好{box[process][j] origin[place[i][j]];}// 接下来看这种摆法是否可行int flag 1; // 初始标记表示可行// 表示遍历某个侧面时是否出现重复颜色used_i[j]标记第i个侧面第j号颜色是否被用过初始清零int used_0[n];int used_1[n];int used_2[n];int used_3[n];for (int i 0; i n; i) //{used_0[i] 0;used_1[i] 0;used_2[i] 0;used_3[i] 0;}for (int i 0; i process; i) // 遍历到现在所有已经放好的立方体查看每个侧面是否有重复的颜色{used_0[box[i][0]];used_1[box[i][1]];used_2[box[i][2]];used_3[box[i][3]];if (used_0[box[i][0]] 1 || used_1[box[i][1]] 1 || used_2[box[i][2]] 1 || used_3[box[i][3]] 1)// 题目要求是最后摆好的整个立方体条的每个侧面都要有n种颜色// 但因为n个立方体摆出的该侧面条有n种颜色所以相当于每个立方体在该侧面的颜色都不一样// 即某个侧面条上每种颜色只能使用一次这里转换了题目的条件// 某个侧面条上某个颜色用了不止一次不符合条件该方案以及该方案的子树剪掉{flag 0;// cout used_0[box[i][0]] used_1[box[i][1]] used_2[box[i][2]] used_3[box[i][3]] endl;break;}}if (flag 1) // 目前所有已经摆好的立方体的每个侧面都没有重复的颜色符合要求可以继续放下一个立方体backtrack(depth 1);}}return;
}int main()
{cin n;for (int i 0; i n; i){cin color[i];}for (int i 0; i n; i){for (int j 0; j 6; j){cin box[i][j];}}cout endl ans endl;backtrack(-1);return 0;
}
▲验证
未找到在线测评使用题目给出的案例
input
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
输出结果如下
ans
Possible Solution 1 :
R B G Y R R
Y R B G R G
B G R B G Y
G Y Y R B BPossible Solution 2 :
B R G Y R R
R Y B G G R
G B R B Y G
Y G Y R B BPossible Solution 3 :
R B Y G R R
Y R G B R G
B G B R G Y
G Y R Y B BPossible Solution 4 :
B R Y G R R
R Y G B G R
G B B R Y G
Y G R Y B BPossible Solution 5 :
Y G R B R R
G B Y R R G
B R B G G Y
R Y G Y B BPossible Solution 6 :
G Y R B R R
B G Y R G R
R B B G Y G
Y R G Y B BPossible Solution 7 :
Y G B R R R
G B R Y R G
B R G B G Y
R Y Y G B B Possible Solution 8 :
G Y B R R R
B G R Y G R
R B G B Y G
Y R Y G B B可见答案不唯一显然可能题目给定的答案在其中之一。
我们这种算法的时间复杂度O(n*24^n)数据量大了之后可能会很慢。
5 算法实现题5-13 任务分配问题
▲问题重述
问题描述: 设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为 cij。试设计一个算法为每一个人都分配1 件不同的工作并使总费用达到最小。
算法设计设计一个算法对于给定的工作费用计算最佳工作分配方案使总费用达到最小。
数据输入第一行有1 个正整数n (1≤n≤20)。接下来的n行每行n个数表示工作费用。
样例
input
3
10 2 3
2 3 4
3 4 5output
9▲解题思路
假设人不动将工作分发给不同人。
解向量x[i]为第i个人被分配第x[i]个工作解空间树为排列树。从第0层开始第0层就有n个节点可以认为第-1层有一个节点答案层在第n层第n-1层将自己与自己交换实际上不影响最终结果。在第n层比较当前总费用是不是比目前保存的方案总费用更少如果是就将这个更小的存下来否则不做处理。
遍历完整个排列树后得到最优解。
▲代码
// -*- coding:utf-8 -*-// File : 5-13.cpp
// Time : 2023/12/25
// Author : wolf#include iostreamusing namespace std;
const int MAXNUM 9999999;
int c[21][21];
int x[21];
int nowcost 0, mincost MAXNUM, n;void swap(int a, int b)
{int temp x[a];x[a] x[b];x[b] temp;
}void backtrack(int depth)
{if (depth n) // 答案层{mincost min(mincost, nowcost);// cout nowcost endl;// 不需要输出解向量故不用保存解向量}else{for (int i depth; i n; i){// depth当前人i为待分发物品序号人不动发物品nowcost c[x[i]][depth];swap(i, depth);backtrack(depth 1);swap(i, depth);nowcost - c[x[i]][depth];}}
}int main()
{cin n;for (int i 0; i n; i){for (int j 0; j n; j){cin c[i][j];}}for (int i 0; i n; i)x[i] i;backtrack(0);cout mincost endl;return 0;
}
▲验证
测试数据可通过。
