前言 主要还是因为我咕咕咕太久了,现在还是期末考试,期末考试有算法考试。所以就拿我算法复习题目做一下解析分析顺带来复习一下。(实在咕咕咕 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; void disp () { printf ("第 %d 个解," , ++cnt); printf ("选取的数为:" ); for (int i=0 ; i<x.size (); i++) { if (x[i] == 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 ); 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 ;void dfs (int cw, int rw, int i) { if (i >= n) { if (cw > bestw) { bestw = cw; bestx = x; } } else { rw -= w[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; vector<vector<int >> A; vector<int > dist; vector<int > pre; void bfs (int s) { dist = vector <int >(n, INF); pre = vector <int >(n); dist[s] = 0 ; queue<int > qu; qu.push (s); while (!qu.empty) { int u = qu.front (); qu.pop (); 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); } } } } } 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; } 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; void bound (QNode& e) { int rw = W - e.cw; double b = e.cv; int j = e.i; while (j<n && g[j].w <= rw) { rw -= g[j].w; b += g[j].v; j ++; } if (j<n) { b += (double ) g[j].v/g[j].w*rw; } e.ub = b; } 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; e1. x = e.x; e1. x[e.1 ] = 1 ; EnQueue (e1, qu); } e2. cw = e.cw; e2. cv = e.cv; e2. i = e.i + 1 ; bound (e2); if (e2. ub > bestv) { EnQueue (e2, qu); } } } void knap (vector<Goods> g1, int W1) { g = g1; W = W1; n = g.size (); 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()) ; for (int i = n - 2 ; i >= 0 ; --i) { for (int j = 0 ; j <= i; ++j) { dp[j] = triangle[i][j] + min (dp[j], dp[j + 1 ]); } } 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 (); vector<vector<int >> dp (m + 1 , vector <int >(n + 1 , 0 )); 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 ; } else { dp[i][j] = max (dp[i - 1 ][j], dp[i][j - 1 ]); } } } return dp[m][n]; } int main () { string a = "abcde" ; string b = "ace" ; int result = longestCommonSubsequence (a, b); cout << "最长公共子序列的长度是: " << result << endl; return 0 ; }