前言

主要还是因为我咕咕咕太久了,现在还是期末考试,期末考试有算法考试。所以就拿我算法复习题目做一下解析分析顺带来复习一下。(实在咕咕咕 hhh,更新一下心理负担没那么大 hhh)。

我后面可能会再改一改,加上一些解释。现在先发

算法解析

子集和问题

给定 n 个不同的正整数集合 $a={a0, a_1, …, a{n-1}}$ 和一个正整数 $t$,要求找出 $a$ 的子集,使该子集中所有元素的和为 $t$。例如,当 $t=4$ 时,$a={3,1,5,2}$,$t=8$ 则满足要求的子集 $s$ 为 ${3,5}$ 和 ${1,5,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
int n,t;
vector<int> a;
int cnt=0;
int tot=0;
vector<int> x;

// 输出一个解,这一个函数就是确定当前的解向量就是所需的向量内容,按照 x[i]==1 输出最后的结果
void disp() {
printf("第 %d 个解,", ++cnt);
printf("选取的数为:");
for (int i=0; i<x.size(); i++) {
if (x[i] == 1) { // 这里选择的是解向量如果取 1,则代表取这一个值
printf("%d ", a[i]); // 取到的这一个值作为输出
}
}
printf("\n");
}

// 回溯算法
void dfs(int cs, int i) {
tot++; // 计算总的调用次数(用于调优,写考试题目忽略)
if (i>=n) {
if (cs==t) disp(); // 找到一个满足条件的解
} else { // 这一部分指的是还没有到叶子节点,继续回溯(回调)
x[i] = 1;
dfs(cs+a[i], i+1); // 向左分支添加,左分支指的是选择当前 i 对应数,进行添加
x[i] = 0;
dfs(cs, i+1); // 向右分支添加,右分支指的是不选择数字,直接下一个
}
}

void subs1(vector<int>& A, int T) {
n = A.size();
a = A;
t = T;
x = vector<int>(n);
printf("求解结果\n");
dfs(0,0);
printf("tot=%d\n", tot);
}

解空间树

简单装载问题

有 $n$ 个集装箱要装上一艘载重量为 $t$ 的轮船,其中集装箱 $i(0 \leq i \leq n-1)$ 的重量为 $w_1$。不考虑集装箱的体积限制,现要选出重量和小于或等于 $t$ 并且尽可能重的若干集装箱装上轮船。例如,$n=5, t=10, w={5,2,6,4,3}$ 时,其最佳装载方案有两种,即 ${1,1,0,0,1}$ 和 ${0,0,1,1,0}$,对应集装箱的重量和达到最大值 $t$。

算法

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
vector<int> w;
int t;
int n;
vector<int> x;
vector<int> bestx;
int bestw = 0;

// 回溯算法,cw 指的是当前已经集装箱载重的总重,rw 指的是剩余货物的总重量,
// i 表示当前选择了第几个集装箱
void dfs(int cw, int rw, int i) {
// 是否已经出于叶子节点末端,如果是末端就要计算总重
if (i >= n) {
// 检查哪一个是最优的重量
if (cw > bestw) {
bestw = cw;
bestx = x;
}
} else {
// 减去的目的是假设如果选择了当前,获取剩余的总重量。
// 目的是右剪枝如果已经小于最大值就没必要继续执行了。
// 因为总共加起来一定小于最右的右侧部分,当前的承重加上现在第 i 个集装箱重量是否小于总承载。
rw -= w[i];
// 当前的承重加上现在第 i 个集装箱重量是否小于总承载。
// 若小于总承载就可以继续往下添加集装箱或者刚好满了。
if (cw + w[i] <= t) {
x[i] = 1;
// 添加集装箱然后到下一个集装件再检查可不可以再添加
cw += w[i];
dfs(cw, rw, i+1);
}
// 检查当前集装箱的重量和剩余集装箱的重量是否大于当前,最优的重量,如果小于当前最优的重量,
// 就代表剩余的货物和已经计算过的目前最大承重货物太小了,我要取最优的一种结果,
// 他已经不是最优了,往下也不会了,没必要比较了。
if (cw + rw > bestw) {
x[i] = 0;
// 如果大于最优的,就说明下面的组合有可能会替代最优的方案,
// 所以可以往下继续执行尝试一下是否可以添加
dfs(cw, rw, i);
}
}
}

void loading(vector<int>& W, int T) {
w = W;
t = T;
n = w.size();
int rw = 0;
for (int i=0; i<n; i++) {
rw += w[i];
}
x = vector<int>(n);
dfs(0, rw, 0);
printf("求解结果\n");
for(int i=0; i<n; i++) {
// 这里是当前最优的结果,获取最优结果选择的集装箱
if (bestx[i] == 1) {
printf("选取第 %d 个集装箱\n", i);
}
}
printf("总重量%d\n", bestw);
}

图的单源最短路径

给定一个带权有向图 $G=(V,E)$,其中每条边的权是一个正整数。另外给定 $V$ 中的一个定点 $s$,称之为源点。计算从源点到其他所有各定点的最短路径及其长度。这里的路径长度指的是路径上各边的权之和。

算法

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
int n;							// n 的定义来自于检查邻接矩阵内的一维数组个数(顶点数)
vector<vector<int>> A; // 图的邻接矩阵
vector<int> dist; // 这个 dist 是对应从源 s 位置到目标位置的权(最小)
vector<int> pre; // 这个 pre 是最短路径中要到达这个目标上一个顶点应该是什么

// 该 bfs 中,指的是开始位置 s (如 0),然后根据这个 0 依照邻接矩阵的走法来依次进队出队
// 直到最后无法入队,则说明路程已经全部走完了,没有下一步可走了
void bfs(int s) {
dist = vector<int>(n, INF);
pre = vector<int>(n);
// 代表开始位置到开始位置一定为 0
dist[s] = 0;
queue<int> qu;
// 队列进入一个开始源 s
qu.push(s);
while(!qu.empty) {
int u = qu.front();
qu.pop();
// 首先我们确定 A[u][v] 可以理解为 u 是相对起始源,而 v 是 u 作为起点的相对终点目标
// 那么对应 v 也是不能超过顶点个数的,所以不能大于 n
for (int v=0; v<n; v++) {
// 该判断代表这个相对源到目标是有权的(即有路可走),否则就是不可达,不能到达
if (A[u][v] != 0 && A[u][v] != INF) {
// 检查这一个走法是不是比之前的走法更好(即权最小)
if (dist[u] + A[u][v] < dist[v]) {
dist[v] = dist[u] + A[u][v];
// 我现在已经从一个相对源走到了对应目标
// 我现在要以这一个目标作为相对起点尝试继续往下走。
pre[v] = u;
qu.push(v);
}
}
}
}
}

// 这一个算法就是去检查所有从源到各个目标的路径,最短权是什么,然后输出出来
// s 代表是开始位置(源),i 就是我要到的目标
void dispapath(int s, int i) {
vector<int> path;
if (s == i) return;
if (dist[i] == INF) {
printf("源点 %d 到顶点 %d 没有路径\n", s, i);
} else {
// 获取这个到这个目标的相对开始源(即我如何到这个目标的上一个节点)
int k = pre[i];
// 把他放入队列中
path.push_back(i);
// 如果这个上一个目标不是来自于开始源
// 那就代表当前目标的前一个相对源不是开始而是另外一个相对目标,也有对应的相对开始源
while (k != s) {
path.push_back(k);
k = pre[k];
}
// 算上开始(源)
path.push_back(s);
printf("源点 %d 到顶点 %d 的最短路径长度:%d,路径为:", s, i, dist[i]);
for (int j=path.size()-1; j>=0; j--) {
printf("%d ", path[j]);
}
printf("\n");
}
}

void solve(vector<vector<int>>& a, int s) {
A = a;
x = A.size();
}

0/1背包问题

有 $n$ 个物品,物品的编号为 $0 \sim n-1$ ,重量集合为 ${w0, w_1, …, w{n-1}}$,价值集合为 ${v0, v_1, …, v{n-1}}$ ,给定一个容量为 $W$ 的背包。现在从这些物品中选取若干物品装入该背包,每个物品要么选中要么不选中,要求选中物品的总重量不超过背包容量并且有最大的价值,求出该最大价值和一个装入方案(如果有多个装入方案,找到一个即可),并结合如表所示的 4 个物品(背包容量 $W=6$)进行求解。

物品的编号 重量 价值
0 5 4
1 3 4
2 2 3
3 1 1

算法

队列节点

1
2
3
4
5
6
7
struct QNode {
int i; // 当前层次(物品序号)
int cw; // 当前总重量
int cv; // 当前总价值
vector<int> x; // 当前解向量
double ub; // 上届
}

物品

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Goods {
int no; // 物品的编号
int w; // 物品的重量
int v; // 商品的价值

Goods(int no, int w, int v) {
this->no = no;
this->w = w;
this->v = v;
}

// 这一个算法是用作下面算法中 sort 进行排序使用的,会根据这个算法来进行算法的排序操作
bool operator< (const Goods& s) const {
return (double) v/w > (double)s.v/s.w;
}
}

最后算法

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
vector<Goods> g;		// 全部物品
int W; // 背包容量
int n; // 物品个数
vector<int> bestx; // 存放最优解向量
int bestv = 0; // 最优的总价值
int bestw; // 最优的总重量

// 这一个函数是计算上届最大价值量,表示的是排序(v/w)后的比然后计算可以领取到的最大价值容量
// 因为已经通过了 sort 进行排序,而且排序是递减通过 v/w 的,所以按照 bound 函数计算的内容
// 一定是最高的价值
void bound(QNode& e) {
// 用户获取剩余的重量
int rw = W - e.cw;
// 获取当前的价值
double b = e.cv;
// 当前背包的价值
int j = e.i;
// 在这一个循环中是处理根据剩余容量去提取排序后的商品容量,举个例子
// 我现在的剩余容量为 5,第一个商品(j = e.i)的重量为 4,价值为 2
// 下一个商品(j = ++e.i)重量为 1,价值为 1
// 这个循环就是根据商品的内容去检查容量然后进行添加操作,剩余容量 5-4=1 执行循环
// 价值增加,剩余容量减少。然后再次循环检查 1-1=0 符合,执行循环,价值增加剩余容量减少
// 最后获得的总容量 b = b+2+1
while (j<n && g[j].w <= rw) {
rw -= g[j].w;
b += g[j].v;
j ++;
}
// 这一部分是如果上述的物品重量大于剩余背包容量,而背包没有被填满。那么就会进行第二步操作。
// 将下一个商品取出部分等于 rw 部分,直接填入,其中价值计算就是 v/w 单位重量的价值乘以剩余容量
// 就是这个部分商品的总价值
if (j<n) {
b += (double) g[j].v/g[j].w*rw;
}
// 最后获得的结果就是这个节点以及之后的最高价值上届(称为上届)
e.ub = b;
}

// 节点 e 进队的操作
// 获取当前这个节点检查是不是叶子节点,如果是叶子节点就进行判断当前的叶子节点是不是最优的取物品
// 如果是,就会替换原有的最优。
// 如果不是叶子节点,就会进队,等待下一次进行 bfs 内循环检查左右分支,继续分,直到分到叶子节点
void EnQueue(QNode& e) {
// 判断用于检查是否达到叶子节点
if (e.i == n) {
if (e.cv > bestv) {
bestv = e.cw;
bestx = e.x;
vesrw = e.cw;
}
} else {
qu.push(e);
}
}

void bfs() {
QNode e, e1, e2;
queue<QNode> qu;
// 刚刚进入初始化的内容,就是什么东西都没有拿,也没有价值的时候
e.i = 0;
e.x = vector<int>(n, 0);
e.cw = 0; e.cv = 0;
qu.push(e);
while (!qu.empty()) {
e = qu.front();
qu.pop();
// 这一步条件为左剪枝,用于检查当前已选的重量加上下一个物品的重量,是否会超过当前背包容量。
// 如果会超过当前背包的容量,就表明如果下一个物品拿走之后,接下来的所有左分支和右分支
// 无论怎么进行添加,总重量都会超过当前背包的容量,所以就没有必要继续执行了,
// 直接不需要这一块的分支了。
if (e.cw + g[e.i].w <= W) {
e1.cw = e.cw + g[e.i].w;
e1.cv = e.cv + g[e.i].v;
// 既然我不进行左剪枝,那就代表这一个左分支(左节点)是可以要的,所以这个解空间向量
// 就会被提取出来,并且选中(x=1 表示我选择了当前的物品)
e1.x = e.x;
e1.x[e.1] = 1;
// 最后执行进队准备下一次循环进行左右分支的添加或者对左右分支进行剪枝操作进行预备队列
EnQueue(e1, qu);
}
// 右分支指的是我不选择当前的物品,所以就不具有容量和重量,那就是我只获取当前已有的
// 就不需要加入 g[xxx].w 和 g[xxx].v 的内容。
e2.cw = e.cw;
e2.cv = e.cv;
e2.i = e.i + 1;

// 进行价值量上届计算,这个计算是用于检查下一步,有没有必要进行右剪枝操作。
// 如果进行上届计算,然后根据已有的最优价值进行比较。最优的价值已经完全大于了总价值量,
// 那就没必要继续计算了,已经存在更好了,就不需要计算不满足更好的这一个分支了(优化)。
// 假设上届为 6.6 而 bestv 是 8,那么已经有最好的 8 就不需要最大只有 6.6 的部分了。
bound(e2);
if (e2.ub > bestv) {
EnQueue(e2, qu);
}
}
}

void knap(vector<Goods> g1, int W1) {
g = g1;
W = W1;
n = g.size();
// 修改了商品的排列顺序,根据价值比 v/w 进行排列的
// 这一个排列收到了结构体 Goods 中 operater 影响
sort(g.begin(), g.end());
bfs();
printf("最佳装填方案 \n");
for (int i=0; i<n; i++) {
if (bestx[i] == 1) {
printf("选取第 %d 个物品\n", g[i].no);
}
}
printf("总重量=%d, 总价值=%d\n", bestw, bestv);
}

三角形的最小路径和

给定一个高度为 $n$ 的整数三角形,求从顶部到底部的最小路径和,注意从每个整数出发只能向下移动到相邻的整数。例如,如图所示一个 $n=4$ 的三角形,最小路径和为 $13$,对应的路径序列是 $2,3,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
30
31
32
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<int> dp(triangle.back()); // 初始化 dp 数组为最后一行

// 从倒数第二行开始向上计算最小路径和
for (int i = n - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
// dp[j] 更新为当前路径最小值
dp[j] = triangle[i][j] + min(dp[j], dp[j + 1]);
}
}

// 最终的最小路径和存储在 dp[0] 中
return dp[0];
}

int main() {
vector<vector<int>> triangle = {
{2, 0, 0, 0},
{3, 4, 0, 0},
{6, 5, 7, 0},
{8, 3, 9, 2}
};

cout << "最小路径和: " << minimumTotal(triangle) << endl;
return 0;
}

最长公共子序列

一个字符串的子序列是指从该字符串中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后得到的字符序列。例如“ace”是“abcde”的子序列,但“aec”不是“abcde”的子序列。给定两个字符串 a 和 b,称字符串 c 是 a 和 b 的公共子序列是指 c 同是 a 和 b 的子序列。该问题是求两个字符串 a 和 b 的最长公共子序列(LCS)。

算法

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
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int longestCommonSubsequence(const string& a, const string& b) {
int m = a.length();
int n = b.length();

// 创建二维 DP 数组
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

// 填充 DP 数组
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1; // 字符相等,最长公共子序列长度增加 1
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // 字符不等,取最大值
}
}
}

// 返回 LCS 的长度
return dp[m][n];
}

int main() {
string a = "abcde";
string b = "ace";

int result = longestCommonSubsequence(a, b);
cout << "最长公共子序列的长度是: " << result << endl;

return 0;
}