算法》第2章 贪心算法 读书笔记"/>
《趣学算法》第2章 贪心算法 读书笔记
14天阅读挑战赛
算法知识点——贪心算法 2.1
贪心算法：局部最优，而非整体最优
- 贪心选择性质：
整体最优解能通过一系列局部最优的选择得到，选择依赖于已做出的选择而不依赖未做出的选择，无回溯过程。
- 最优子结构性质：
问题的最优解包含其子问题的最优解。
算法题目——最优装载问题（p37）2.2&2.3
背包问题：物品可分割的装载问题。
0-1背包问题：物品不可分割的装载问题——不具有贪心选择性质，一系列局部最优选择得到最优解的近似解。
总重量一定，装载数量最大：局部最优=全局最优。（优先取重量小）
总重量一定，价值最大，可分割：局部最优=全局最优。（优先取性价比高）
总重量一定，价值最大，不可分割：局部最优不等于全局最优。
算法题目——会议安排问题 2.4
目标：在有限时间内召开尽可能多的会议。
贪心策略：每次从剩下会议中选择最早结束时间（最早开始时间+最短持续时间）且与已安排会议相容的会议安排。
代码：
#include <iostream> #include <algorithm> #include <cstring> using namespace std; struct Meet {int beg;int end;int num; } meet[1000]; class setMeet { public:void init();void solve();private:int n, ans; }; void setMeet::init() {int s, e;cout << "输入会议总数" << endl;cin >> n;int i;cout << "输入会议开始时间和结束时间，以空格分开：" << endl;for (i = 0; i < n; i++){cin >> s >> e;meet[i].beg = s;meet[i].end = e;meet[i].num = i + 1;} } bool cmp(Meet x, Meet y) {if (x.end == y.end)return x.beg > y.beg;return x.end < y.end; } void setMeet::solve() {sort(meet, meet + n, cmp);cout << "排完序的会议时间如下：" << endl;int i;cout << "会议编号 开始时间 结束时间" << endl;for (i = 0; i < n; i++)cout << " " << meet[i].num << "\t" << meet[i].beg << "\t" << meet[i].end << endl;cout << "---------------------------------------" << endl;cout << "选择的会议的过程：" << endl;cout << " 选择第" << meet[0].num << "个会议" << endl;ans = 1;int last = meet[0].end;for (i = 1; i < n; ++i){if (meet[i].beg >= last){ans++;last = meet[i].end;cout << " 选择第" << meet[i].num << "个会议" << endl;}}cout << "最多可以安排" << ans << "个会议" << endl; } int main() {setMeet sm;sm.init();sm.solve();return 0; }样例输入：
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
#include <cstdio> #include <iostream> #include <cstring> #include <windows.h> #include <stack> using namespace std; const int N = 100; const int INF = 1e7; int map[N][N], dist[N], p[N], n, m; bool flag[N]; void Dijkstra(int u) {for (int i = 1; i <= n; i++){dist[i] = map[u][i];flag[i] = false;if (dist[i] == INF)p[i] = -1;elsep[i] = u;}dist[u] = 0;flag[u] = true;for (int i = 1; i <= n; i++){int temp = INF, t = u;for (int j = 1; j <= n; j++)if (!flag[j] && dist[j] < temp){t = j;temp = dist[j];}if (t == u)return;flag[t] = true;for (int j = 1; j <= n; j++)if (!flag[j] && map[t][j] < INF)if (dist[j] > (dist[t] + map[t][j])){dist[j] = dist[t] + map[t][j];p[j] = t;}} } void findpath(int u) {int x;stack<int> s;cout << "源点为：" << u << endl;for (int i = 1; i <= n; i++){x = p[i];while (x != -1){s.push(x);x = p[x];}cout << "源点到其他各顶点最短路径为：";while (!s.empty()){cout << s.top() << "--";s.pop();}cout << i << ";最短举例为：" << dist[i] << endl;} } int main() {int u, v, w, st;system("color 0d");cout << "请输入城市的个数：" << endl;cin >> n;cout << "请输入城市之间路线的个数：" << endl;cin >> m;cout << "请输入城市之间的路线和距离：" << endl;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)map[i][j] = INF;while (m--){cin >> u >> v >> w;map[u][v] = min(map[u][v], w);}cout << "请输入小明所在的位置：" << endl;cin >> st;Dijkstra(st);cout << "小明所在的位置：" << st << endl;for (int i = 1; i <= n; i++){cout << "小明：" << st << " - "<< "要去的位置：" << i << endl;if (dist[i] == INF)cout << "sorry,无路可达" << endl;elsecout << "最短距离为：" << dist[i] << endl;}findpath(st);return 0; }输入：
请输入城市的个数：
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
目标：以字符的使用频率为权重构建哈夫曼树，利用哈夫曼树对字符编码。将要编码的字符作为叶子结点，使用频率作为叶子结点的权值。权值越大的叶子离根越近。
贪心策略：每次从树的集合中取出没有双亲且权值最小的两棵左右子树。
代码：
#include <iostream> #include <algorithm> #include <cstring> #include <cstdlib> using namespace std; #define MAXBIT 100 #define MAXVALUE 10000 #define MAXLEAF 30 #define MAXNODE MAXLEAF * 2 - 1 typedef struct {double weight;int parent;int lchild;int rchild;char value; } HNodeType; typedef struct {int bit[MAXBIT];int start; } HCodeType; HNodeType HuffNode[MAXNODE]; HCodeType HuffCode[MAXLEAF]; void HuffmanTree(HNodeType HuffNode[MAXNODE], int n) {int i, j, x1, x2;double m1, m2;for (i = 0; i < 2 * n - 1; i++){HuffNode[i].weight = 0;HuffNode[i].parent = -1;HuffNode[i].lchild = -1;HuffNode[i].rchild = -1;}for (i = 0; i < n; i++){cout << "Please input value and weight of leaf node " << i + 1 << endl;cin >> HuffNode[i].value >> HuffNode[i].weight;}for (i = 0; i < n - 1; i++){m1 = m2 = MAXVALUE;x1 = x2 = 0;for (j = 0; j < n + i; j++){if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1){m2 = m1;x2 = x1;m1 = HuffNode[j].weight;x1 = j;}else if (HuffNode[j].weight < m2 && HuffNode[j].parent == -1){m2 = HuffNode[j].weight;x2 = j;}}HuffNode[x1].parent = n + i;HuffNode[x2].parent = n + i;HuffNode[n + i].weight = m1 + m2;HuffNode[n + i].lchild = x1;HuffNode[n + i].rchild = x2;cout << "x1.weight and x2.weight in round " << i + 1 << "\t" << HuffNode[x1].weight << "\t" << HuffNode[x2].weight << endl;} } void HuffmanCode(HCodeType HuffCode[MAXLEAF], int n) {HCodeType cd;int i, j, c, p;for (i = 0; i < n; i++){cd.start = n - 1;c = i;p = HuffNode[c].parent;while (p != -1){if (HuffNode[p].lchild == c)cd.bit[cd.start] = 0;elsecd.bit[cd.start] = 1;cd.start--;c = p;p = HuffNode[c].parent;}for (j = cd.start + 1; j < n; j++)HuffCode[i].bit[j] = cd.bit[j];HuffCode[i].start = cd.start;} } int main() {int i, j, n;cout << "Please input n: " << endl;cin >> n;HuffmanTree(HuffNode, n);HuffmanCode(HuffCode, n);for (i = 0; i < n; i++){cout << HuffNode[i].value << ": Huffman code is: ";for (j = HuffCode[i].start + 1; j < n; j++)cout << HuffCode[i].bit[j];cout << endl;}return 0; }样例输入：
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，从连接两个集合的边中选择一条权值最小的边。
代码：
#include <iostream> using namespace std; const int INF = 0x3fffffff; const int N = 100; bool s[N]; int closest[N]; int lowcost[N]; void Prim(int n, int u0, int c[N][N]) {s[u0] = true;int i;int j;for (i = 1; i <= n; i++){if (i != u0){lowcost[i] = c[u0][i];closest[i] = u0;s[i] = false;}elselowcost[i] = 0;}for (i = 1; i <= n; i++){int temp = INF;int t = u0;for (j = 1; j <= n; j++){if ((!s[j]) && (lowcost[j] < temp)){t = j;temp = lowcost[j];}}if (t == u0)break;s[t] = true;for (j = 1; j <= n; j++){if ((!s[j]) && (c[t][j] < lowcost[j])){lowcost[j] = c[t][j];closest[j] = t;}}} } int main() {int n, c[N][N], m, u, v, w;int u0;cout << "输入结点数n和边数m：" << endl;cin >> n >> m;int sumcost = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)c[i][j] = INF;cout << "输入结点数u，v和边值w：" << endl;for (int i = 1; i <= m; i++){cin >> u >> v >> w;c[u][v] = c[v][u] = w;}cout << "输入任一结点u0：" << endl;cin >> u0;Prim(n, u0, c);cout << "数组lowcost的内容为：" << endl;for (int i = 1; i <= n; i++)cout << lowcost[i] << " ";cout << endl;for (int i = 1; i <= n; i++)sumcost += lowcost[i];cout << "最小的花费是：" << sumcost<< endl;return 0; }样例输入：
输入结点数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
更多推荐
《趣学算法》第2章 贪心算法 读书笔记
发布评论