《趣学算法》第2章 贪心算法 读书笔记
发布时间
阅读量：
阅读量
算法知识点——贪心算法 2.1
贪心算法：局部最优，而非整体最优
- 贪心选择性质：
整体最优解能通过一系列局部最优的选择得到，选择依赖于已做出的选择而不依赖未做出的选择，无回溯过程。
- 最优子结构性质：
问题的最优解包含其子问题的最优解。
算法题目——最优装载问题（p37）2.2&2.3
背包问题：物品可分割的装载问题。
0-1背包问题：物品不可分割的装载问题——不具有贪心选择性质，一系列局部最优选择得到最优解的近似解。
总重量一定，装载数量最大：局部最优=全局最优。（优先取重量小）
总重量一定，价值最大，可分割：局部最优=全局最优。（优先取性价比高）
总重量一定，价值最大，不可分割：局部最优不等于全局最优。
算法题目——会议安排问题 2.4
目标：在有限时间内召开尽可能多的会议。
贪心策略：每次从剩下会议中选择最早结束时间（最早开始时间+最短持续时间）且与已安排会议相容的会议安排。
代码：
> 1. #include <iostream>
>
> 2. #include <algorithm>
>
> 3. #include <cstring>
>
> 4. using namespace std;
>
> 5. struct Meet
>
> 6. {
>
> 7. int beg;
>
> 8. int end;
>
> 9. int num;
>
> 10. } meet[1000];
>
> 11. class setMeet
>
> 12. {
>
> 13. public:
>
> 14. void init();
>
> 15. void solve();
>
> 16.
>
> 17. private:
>
> 18. int n, ans;
>
> 19. };
>
> 20. void setMeet::init()
>
> 21. {
>
> 22. int s, e;
>
> 23. cout << "输入会议总数" << endl;
>
> 24. cin >> n;
>
> 25. int i;
>
> 26. cout << "输入会议开始时间和结束时间，以空格分开：" << endl;
>
> 27. for (i = 0; i < n; i++)
>
> 28. {
>
> 29. cin >> s >> e;
>
> 30. meet[i].beg = s;
>
> 31. meet[i].end = e;
>
> 32. meet[i].num = i + 1;
>
> 33. }
>
> 34. }
>
> 35. bool cmp(Meet x, Meet y)
>
> 36. {
>
> 37. if (x.end == y.end)
>
> 38. return x.beg > y.beg;
>
> 39. return x.end < y.end;
>
> 40. }
>
> 41. void setMeet::solve()
>
> 42. {
>
> 43. sort(meet, meet + n, cmp);
>
> 44. cout << "排完序的会议时间如下：" << endl;
>
> 45. int i;
>
> 46. cout << "会议编号 开始时间 结束时间" << endl;
>
> 47. for (i = 0; i < n; i++)
>
> 48. cout << " " << meet[i].num << "\t" << meet[i].beg << "\t" << meet[i].end << endl;
>
> 49. cout << "---------------------------------------" << endl;
>
> 50. cout << "选择的会议的过程：" << endl;
>
> 51. cout << " 选择第" << meet[0].num << "个会议" << endl;
>
> 52. ans = 1;
>
> 53. int last = meet[0].end;
>
> 54. for (i = 1; i < n; ++i)
>
> 55. {
>
> 56. if (meet[i].beg >= last)
>
> 57. {
>
> 58. ans++;
>
> 59. last = meet[i].end;
>
> 60. cout << " 选择第" << meet[i].num << "个会议" << endl;
>
> 61. }
>
> 62. }
>
> 63. cout << "最多可以安排" << ans << "个会议" << endl;
>
> 64. }
>
> 65. int main()
>
> 66. {
>
> 67. setMeet sm;
>
> 68. sm.init();
>
> 69. sm.solve();
>
> 70. return 0;
>
> 71. }
>
>
>
>
> ```
>
>
>
> 样例输入：
> 10
> 3 6
> 1 4
> 5 7
> 2 5
> 5 9
> 3 8
> 8 11
> 6 10
> 8 12
> 12 14
>
>
>
>
>
> 样例输出：
> 排完序的会议时间如下：
> 会议编号 开始时间 结束时间
> 2 1 4
> 4 2 5
> 1 3 6
> 3 5 7
> 6 3 8
> 5 5 9
> 8 6 10
> 7 8 11
> 9 8 12
> 10 12 14
> \---------------------------------------
> 选择的会议的过程：
> 选择第2个会议
> 选择第3个会议
> 选择第7个会议
> 选择第10个会议
> 最多可以安排4个会议
>
>
### 算法题目——最短路径问题 Dijkstra 2.5
>
1. #include <cstdio>
2. #include <iostream> 3. #include <cstring> 4. #include <windows.h> 5. #include <stack> 6. using namespace std; 7. const int N = 100; 8. const int INF = 1e7; 9. int map[N][N], dist[N], p[N], n, m; 10. bool flag[N]; 11. void Dijkstra(int u) 12. { 13. for (int i = 1; i <= n; i++) 14. { 15. dist[i] = map[u][i]; 16. flag[i] = false; 17. if (dist[i] == INF) 18. p[i] = -1; 19. else 20. p[i] = u; 21. } 22. dist[u] = 0; 23. flag[u] = true; 24. for (int i = 1; i <= n; i++) 25. { 26. int temp = INF, t = u; 27. for (int j = 1; j <= n; j++) 28. if (!flag[j] && dist[j] < temp) 29. { 30. t = j; 31. temp = dist[j]; 32. } 33. if (t == u) 34. return; 35. flag[t] = true; 36. for (int j = 1; j <= n; j++) 37. if (!flag[j] && map[t][j] < INF) 38. if (dist[j] > (dist[t] + map[t][j])) 39. { 40. dist[j] = dist[t] + map[t][j]; 41. p[j] = t; 42. } 43. } 44. } 45. void findpath(int u) 46. { 47. int x; 48. stack<int> s; 49. cout << "源点为：" << u << endl; 50. for (int i = 1; i <= n; i++) 51. { 52. x = p[i]; 53. while (x != -1) 54. { 55. s.push(x); 56. x = p[x]; 57. } 58. cout << "源点到其他各顶点最短路径为："; 59. while (!s.empty()) 60. { 61. cout << s.top() << "--"; 62. s.pop(); 63. } 64. cout << i << ";最短举例为：" << dist[i] << endl; 65. } 66. } 67. int main() 68. { 69. int u, v, w, st; 70. system("color 0d"); 71. cout << "请输入城市的个数：" << endl; 72. cin >> n; 73. cout << "请输入城市之间路线的个数：" << endl; 74. cin >> m; 75. cout << "请输入城市之间的路线和距离：" << endl; 76. for (int i = 1; i <= n; i++) 77. for (int j = 1; j <= n; j++) 78. map[i][j] = INF; 79. while (m--) 80. { 81. cin >> u >> v >> w; 82. map[u][v] = min(map[u][v], w); 83. } 84. cout << "请输入小明所在的位置：" << endl; 85. cin >> st; 86. Dijkstra(st); 87. cout << "小明所在的位置：" << st << endl; 88. for (int i = 1; i <= n; i++) 89. { 90. cout << "小明：" << st << " - " 91. << "要去的位置：" << i << endl; 92. if (dist[i] == INF) 93. cout << "sorry,无路可达" << endl; 94. else 95. cout << "最短距离为：" << dist[i] << endl; 96. } 97. findpath(st); 98. return 0; 99. }
输入： 请输入城市的个数： 5 请输入城市之间路线的个数： 11 请输入城市之间的路线和距离： 1 5 12 5 1 8 1 2 16 2 1 29 5 2 32 2 4 13 4 2 27 1 3 15 3 1 21 3 4 7 4 3 19 请输入小明所在的位置： 5 输出： 小明所在的位置：5 小明：5 - 要去的位置：1 最短距离为：8 小明：5 - 要去的位置：2 最短距离为：24 小明：5 - 要去的位置：3 最短距离为：23 小明：5 - 要去的位置：4 最短距离为：30 小明：5 - 要去的位置：5 最短距离为：0 源点为：5 源点到其他各顶点最短路径为：5--1;最短举例为：8 源点到其他各顶点最短路径为：5--1--2;最短举例为：24 源点到其他各顶点最短路径为：5--1--3;最短举例为：23 源点到其他各顶点最短路径为：5--1--3--4;最短举例为：30 源点到其他各顶点最短路径为：5;最短举例为：0
算法题目——哈夫曼编码 2.6
目标：以字符的使用频率为权重构建哈夫曼树，利用哈夫曼树对字符编码。将要编码的字符作为叶子结点，使用频率作为叶子结点的权值。权值越大的叶子离根越近。
贪心策略：每次从树的集合中取出没有双亲且权值最小的两棵左右子树。
代码：
> 1. #include <iostream>
>
> 2. #include <algorithm>
>
> 3. #include <cstring>
>
> 4. #include <cstdlib>
>
> 5. using namespace std;
>
> 6. #define MAXBIT 100
>
> 7. #define MAXVALUE 10000
>
> 8. #define MAXLEAF 30
>
> 9. #define MAXNODE MAXLEAF * 2 - 1
>
> 10. typedef struct
>
> 11. {
>
> 12. double weight;
>
> 13. int parent;
>
> 14. int lchild;
>
> 15. int rchild;
>
> 16. char value;
>
> 17. } HNodeType;
>
> 18. typedef struct
>
> 19. {
>
> 20.
>
> 21. int bit[MAXBIT];
>
> 22. int start;
>
> 23. } HCodeType;
>
> 24. HNodeType HuffNode[MAXNODE];
>
> 25. HCodeType HuffCode[MAXLEAF];
>
> 26. void HuffmanTree(HNodeType HuffNode[MAXNODE], int n)
>
> 27. {
>
> 28. int i, j, x1, x2;
>
> 29. double m1, m2;
>
> 30. for (i = 0; i < 2 * n - 1; i++)
>
> 31. {
>
> 32. HuffNode[i].weight = 0;
>
> 33. HuffNode[i].parent = -1;
>
> 34. HuffNode[i].lchild = -1;
>
> 35. HuffNode[i].rchild = -1;
>
> 36. }
>
> 37. for (i = 0; i < n; i++)
>
> 38. {
>
> 39. cout << "Please input value and weight of leaf node " << i + 1 << endl;
>
> 40. cin >> HuffNode[i].value >> HuffNode[i].weight;
>
> 41. }
>
> 42. for (i = 0; i < n - 1; i++)
>
> 43. {
>
> 44. m1 = m2 = MAXVALUE;
>
> 45. x1 = x2 = 0;
>
> 46. for (j = 0; j < n + i; j++)
>
> 47. {
>
> 48. if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1)
>
> 49. {
>
> 50. m2 = m1;
>
> 51. x2 = x1;
>
> 52. m1 = HuffNode[j].weight;
>
> 53. x1 = j;
>
> 54. }
>
> 55. else if (HuffNode[j].weight < m2 && HuffNode[j].parent == -1)
>
> 56. {
>
> 57. m2 = HuffNode[j].weight;
>
> 58. x2 = j;
>
> 59. }
>
> 60. }
>
> 61. HuffNode[x1].parent = n + i;
>
> 62. HuffNode[x2].parent = n + i;
>
> 63. HuffNode[n + i].weight = m1 + m2;
>
> 64. HuffNode[n + i].lchild = x1;
>
> 65. HuffNode[n + i].rchild = x2;
>
> 66. cout << "x1.weight and x2.weight in round " << i + 1 << "\t" << HuffNode[x1].weight << "\t" << HuffNode[x2].weight << endl;
>
> 67. }
>
> 68. }
>
> 69. void HuffmanCode(HCodeType HuffCode[MAXLEAF], int n)
>
> 70. {
>
> 71. HCodeType cd;
>
> 72. int i, j, c, p;
>
> 73. for (i = 0; i < n; i++)
>
> 74. {
>
> 75. cd.start = n - 1;
>
> 76. c = i;
>
> 77. p = HuffNode[c].parent;
>
> 78. while (p != -1)
>
> 79. {
>
> 80. if (HuffNode[p].lchild == c)
>
> 81. cd.bit[cd.start] = 0;
>
> 82. else
>
> 83. cd.bit[cd.start] = 1;
>
> 84. cd.start--;
>
> 85. c = p;
>
> 86. p = HuffNode[c].parent;
>
> 87. }
>
> 88. for (j = cd.start + 1; j < n; j++)
>
> 89. HuffCode[i].bit[j] = cd.bit[j];
>
> 90. HuffCode[i].start = cd.start;
>
> 91. }
>
> 92. }
>
> 93. int main()
>
> 94. {
>
> 95. int i, j, n;
>
> 96. cout << "Please input n: " << endl;
>
> 97. cin >> n;
>
> 98. HuffmanTree(HuffNode, n);
>
> 99. HuffmanCode(HuffCode, n);
>
> 100. for (i = 0; i < n; i++)
>
> 101. {
>
> 102. cout << HuffNode[i].value << ": Huffman code is: ";
>
> 103. for (j = HuffCode[i].start + 1; j < n; j++)
>
> 104. cout << HuffCode[i].bit[j];
>
> 105. cout << endl;
>
> 106. }
>
> 107. return 0;
>
> 108. }
>
>
>
>
> ```
>
>
>
> 样例输入：
> Please input n:
> 6
> Please input value and weight of leaf node 1
> a 0.05
> Please input value and weight of leaf node 2
> b 0.32
> Please input value and weight of leaf node 3
> c 0.18
> Please input value and weight of leaf node 4
> d 0.07
> Please input value and weight of leaf node 5
> e 0.25
> Please input value and weight of leaf node 6
> f 0.13
>
>
>
>
> 样例输出：
>
>
>
> x1.weight and x2.weight in round 1 0.05 0.07
> x1.weight and x2.weight in round 2 0.12 0.13
> x1.weight and x2.weight in round 3 0.18 0.25
> x1.weight and x2.weight in round 4 0.25 0.32
> x1.weight and x2.weight in round 5 0.43 0.57
> a: Huffman code is: 1000
> b: Huffman code is: 11
> c: Huffman code is: 00
> d: Huffman code is: 1001
> e: Huffman code is: 01
> f: Huffman code is: 10
>
>
### 算法题目——最小生成树求解问题 2.7
>
>
> 目标：对于n个顶点的连通图，找出n-1条最小且无回路的边。
>
>
>
> 子图：从原图中选中一些顶点和边组成的图。
>
>
>
> 生成子图：选中一些边和所有顶点组成的图。
>
>
>
> 生成树：生成子图是树。
>
>
>
> 最小生成树：权值之和最小的生成树。
>
>
>
> 贪心策略：避圈法。把已在生成树中的结点看作一个集合U，剩下的看作另一个集合V-U，从连接两个集合的边中选择一条权值最小的边。
>
>
>
> 代码：
>
>
1. #include <iostream>
2. using namespace std; 3. const int INF = 0x3fffffff; 4. const int N = 100; 5. bool s[N]; 6. int closest[N]; 7. int lowcost[N]; 8. void Prim(int n, int u0, int c[N][N]) 9. { 10. s[u0] = true; 11. int i; 12. int j; 13. for (i = 1; i <= n; i++) 14. { 15. if (i != u0) 16. { 17. lowcost[i] = c[u0][i]; 18. closest[i] = u0; 19. s[i] = false; 20. } 21. else 22. lowcost[i] = 0; 23. } 24. for (i = 1; i <= n; i++) 25. { 26. int temp = INF; 27. int t = u0; 28. for (j = 1; j <= n; j++) 29. { 30. if ((!s[j]) && (lowcost[j] < temp)) 31. { 32. t = j; 33. temp = lowcost[j]; 34. } 35. } 36. if (t == u0) 37. break; 38. s[t] = true; 39. for (j = 1; j <= n; j++) 40. { 41. if ((!s[j]) && (c[t][j] < lowcost[j])) 42. { 43. lowcost[j] = c[t][j]; 44. closest[j] = t; 45. } 46. } 47. } 48. } 49. int main() 50. { 51. int n, c[N][N], m, u, v, w; 52. int u0; 53. cout << "输入结点数n和边数m：" << endl; 54. cin >> n >> m; 55. int sumcost = 0; 56. for (int i = 1; i <= n; i++) 57. for (int j = 1; j <= n; j++) 58. c[i][j] = INF; 59. cout << "输入结点数u，v和边值w：" << endl; 60. for (int i = 1; i <= m; i++) 61. { 62. cin >> u >> v >> w; 63. c[u][v] = c[v][u] = w; 64. } 65. cout << "输入任一结点u0：" << endl; 66. cin >> u0; 67. Prim(n, u0, c); 68. cout << "数组lowcost的内容为：" << endl; 69. for (int i = 1; i <= n; i++) 70. cout << lowcost[i] << " "; 71. cout << endl; 72. for (int i = 1; i <= n; i++) 73. sumcost += lowcost[i]; 74. cout << "最小的花费是：" << sumcost 75. << endl; 76. return 0; 77. }
样例输入： 输入结点数n和边数m： 7 12 输入结点数u，v和边值w： 1 2 23 1 6 28 1 7 36 2 3 20 2 7 1 3 4 15 3 7 4 4 5 3 4 7 9 5 6 17 5 7 16 6 7 25 输入任一结点u0： 1 样例输出： 数组lowcost的内容为： 0 23 4 9 3 17 1 最小的花费是：57
全部评论 (0)
还没有任何评论哟~