第16章 贪心算法

最后更新于:2022-04-01 07:35:51

# 一、综述 贪心算法是使所做的选择看起来都是当前最佳的,期望通过所做的局部最优选择来产生出一个全局最优解 最小生成树算法是贪心算法的一个经典的例子 # 二、活动选择问题 ### (1)代码 头文件:https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/include/chapter16/chapter16.h 产品代码:https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter16/chapter16.cpp 测试代码:https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter16/chapter16Test.cpp ### (2)练习 ### 16.1-1 https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter16/Exercise16_1_1.cpp ### 16.1-2 先对每个活动按照它们的开始时间从小到大排序。令初始时i=n+1,其结束时间无限大,每次选择"结束时间比第i个活动的开始时间早的“的最晚开始活动 ~~~ #include <iostream> #include <algorithm> using namespace std; #define N 11 //一个活动用一个结点表示 struct node { int id; int start; int finish; }A[N+1]; bool cmp(node a, node b) { return a.start < b.start; } //16.1-2 void Greedy_Activity_Selector2() { //先对每个活动按照它们的开始时间从小到大排序 sort(A, A+N+1, cmp); int n = N, i = -1, m; for(m = n; m >= 1; m--) { //找到最后一个“结束时间在第i个活动开始之前”的活动 if(i == -1 || A[m].finish <= A[i].start) { //将这个活动作为执行活动 cout<<A[m].id<<' '; //递归第m个活动执行开始之前的贪心策略 i = m; } } cout<<endl; } /* 0 0 //虚构活动a0 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 */ int main() { int i; //输入测试数据 for(i = 0; i <= N; i++) { A[i].id = i; cin>>A[i].start>>A[i].finish; } Greedy_Activity_Selector2(); return 0; } ~~~ ### 16.1-3 见 [算法导论-16.1-3](http://blog.csdn.net/mishifangxiangdefeng/article/details/7747779) 常规算法: 针对一个特定的教室,然后做类似于16.1中的工作,从剩余活动中尽量多地安排活动到这个教室。如果活动安排完了,就不需要更多的教室了。如果活动没有安排完,再选择一个新的教室,做同样的工作,直到所有的活动都安排完。 这个算法的时间复杂度是O(n^2),稍换一个角度,就能得到一个O(nlgn)的算 O(lgn)算法: 针对一个特定的活动,为它选择一个适合的教室。对所有已经选择过的教室,用一个最大堆来维护,比较的依据是在这个教室中最早开始的活动的开始时间 具体步骤是这样的: step1:对所有活动的结束时间从小到大排序 step2:从最后一个活动开始,向第一个活动,依次针对每个活动做以下处理(1)获取堆顶元素的信息(2)如果堆顶的活动开始时间早于当前活动的结束时间,则申请一个新的教室,把活动的开始时间填入其中,再把教室作为一个结点存入堆中(3)如果堆顶的活动开始时间晚于当前活动的结束时间,就把当前活动填入堆顶元素中(4)选择下一个活动,直到所有活动都处理过 # 三、贪心策略的基本内容 ### (1)练习 ### 16.2-2 经典的0-1背包问题 ### 16.2-3 根据假设w_1 <= w_2 <= ... <= w_n并且v_1 >= v_2 >= ... >= v_n。 贪心选择性质:如果该背包问题有解,则一定存在一个最优解包含物品1。 证明:给定一个最优解,如果已经包含物品1,则证明结束。否则用物品1替代背包中任何一个物品i,因为w_1 <= w_i,所以替换一定是可行的;其次,v_1 >= v_i,所以价值一定不会减小。可见替换后仍然是一个最优解。所以从按物品1,2,...的顺序加入背包,直到不能加入为止。 ### 16.2-4 设ai表示第i个加油站一第i-1个加油站的距离。 最后一次加满了油是在第j个站(j初始时为0) 若第k个站满足aj + a|j+1 + …… +ak <= n 且 aj + a|j+1 + …… +a|k+1 > n,那么他应该在第k个站处加油 ### 16.2-5 对所有点进行从小到大的排序,然后每次取值最小的点xi,把区间[xi,xi+1]加入到所求的区间集合中,并把属于区间[xi,xi+1]的点xj从点集中除去。 ### 16.2-6 见[算法导论-16.2-6](http://blog.csdn.net/mishifangxiangdefeng/article/details/7748435) 常规算法: 先求avgi= vi/wi,按照avgi从大到小排序,再贪心选择,时间复杂度为O(nlgn) 改进: 更一般的情况,不需要排序,例如:如果a1, a2,a3是avgi最大的三个物品,如果它们的总量和不大于W,我们是不需要知道它们间的相对顺序的。 O(n)算法: 选择一个物品作为主元,对所有物品进行Paitition操作。将avg 分为三个集合G = {ai: avgi< m}, Q = {ai:avgi= m}, P = {ai: avgi> m}。分别对G, Q, P中元素求和得SG, SQ, SP。 1. 如果W < SG, 则令物体的集合为O = G,对集合O递归进行上述过程。 2. 如果 SG<=W <= SG+SQ,则将集合G中的元素都放入包中,并将集合Q总元素尽可能多的放入包中,结束。 3. 如果 SG+SQ < W, 将G,Q中元素放入包中。令物体集合O = P,总重W = W - SG - SQ。递归进行上述过程。 16.2-7 对集合A和B进行排序,每次取最大值,计算a^b # 四、哈夫曼编码 ### (1)代码 ~~~ #include <iostream> #include "Heap.h" using namespace std; #define N 6 extern int length; int result[N+1]; //哈夫曼树 struct Huffman_Tree { node *root; Huffman_Tree():root(NULL){} }; //哈夫曼编码 void Huffman(unsigned int *A, Huffman_Tree *T) { int n = N; while(n > 1) { //生成一个新的结点 node *z = new node; //选择堆顶元素作为其左结点 z->left = (node *)Heap_Extract_Min(A); //选择堆顶元素作为其右结点 z->right = (node *)Heap_Extract_Min(A); z->p = z->left->p + z->right->p; //将新结点插入堆中 Min_Heap_Insert(A, (unsigned int)z); n--; } //剩下最后一个结点时,这个结点就是树的根结点 T->root = (node *)Heap_Extract_Min(A); } //输出这棵树上每个字母的编码 void PrintTree(node *t, int cnt) { int i; //叶子结点 if(t->data != -1) { //输出其值及编码 cout<<t->data<<' '; for(i = 0; i < cnt; i++) cout<<result[i]; cout<<endl; return ; } //非叶子结点,对其孩子进行递归 result[cnt] = 0; PrintTree(t->left, cnt+1); result[cnt] = 1; PrintTree(t->right, cnt+1); } /* f 5 e 9 c 12 b 13 d 16 a 45 */ int main() { unsigned int A[N+1] = {};//存储的是结点的地址 length = N; int i; char c; double p; //构造N个结点 for(i = 1; i <= N; i++) { cin>>c>>p; node *z = new node(c, p); A[i] = (unsigned int)z; } //构造最小堆 Build_Min_Heap(A); //构造哈夫曼树 Huffman_Tree *T = new Huffman_Tree(); Huffman(A, T); //输出编码结果 PrintTree(T->root, 0); return 0; } ~~~ ### (2)习题 ### 16.3-2 能 ### 16.3-6 ~~~ #include <iostream> #include "Heap.h"//选择p最小的结点时要借助于堆来实现 using namespace std; #define N 6 extern int length; int result[N+1]; //哈夫曼树 struct Huffman_Tree { node *root; Huffman_Tree():root(NULL){} }; //哈夫曼编码 void Huffman(unsigned int *A, Huffman_Tree *T) { int n = N; while(n > 1) { //生成一个新的结点 node *z = new node; if(n--) { //选择堆顶元素作为其左结点 z->left = (node *)Heap_Extract_Min(A); z->p = z->p + z->left->p; } if(n--) { //选择堆顶元素作为其中间结点 z->middle = (node *)Heap_Extract_Min(A); z->p = z->p + z->middle->p; } if(n--) { //选择堆顶元素作为其右结点 z->right = (node *)Heap_Extract_Min(A); z->p = z->p + z->right->p; } //将新结点插入堆中 Min_Heap_Insert(A, (unsigned int)z); n++; } //剩下最后一个结点时,这个结点就是树的根结点 T->root = (node *)Heap_Extract_Min(A); } //输出这棵树上每个字母的编码 void PrintTree(node *t, int cnt) { int i; //叶子结点 if(t->data != -1) { //输出其值及编码 cout<<t->data<<' '; for(i = 0; i < cnt; i++) cout<<result[i]; cout<<endl; return ; } //非叶子结点,对其孩子进行递归 result[cnt] = 0; PrintTree(t->left, cnt+1); result[cnt] = 1; PrintTree(t->middle, cnt+1); if(t->right) { result[cnt] = 2; PrintTree(t->right, cnt+1); } } /* f 5 e 9 c 12 b 13 d 16 a 45 */ int main() { unsigned int A[N+1] = {};//存储的是结点的地址 length = N; int i; char c; double p; //构造N个结点 for(i = 1; i <= N; i++) { cin>>c>>p; node *z = new node(c, p); A[i] = (unsigned int)z; } //构造最小堆 Build_Min_Heap(A); //构造哈夫曼树 Huffman_Tree *T = new Huffman_Tree(); Huffman(A, T); //输出编码结果 PrintTree(T->root, 0); return 0; } ~~~ # 五、思考题 ### 16-1 找换硬币 a)每次都尽量选最大的、 c)1 4 5 d)找换i分钱的最少硬币数是ans[i],ans[i] = max{ans[i-s[j]]+1} ~~~ #include <iostream> #include <algorithm> using namespace std; //用于排序 bool cmp(int a, int b) { return a < b; } int main() { int n, k, i, j; //输入数据 cin>>n>>k; int s[100], ans[100]; for(i = 0; i < k; i++) cin>>s[i]; //对硬币从小到大排序 sort(s, s + k, cmp); //找换i分钱的最少硬币数是ans[i] memset(ans, 0, sizeof(ans)); //ans[i] = max{ans[i-s[j]]+1} for(i = 1; i <= n; i++) { for(j = 0; s[j] <= i; j++) { if(ans[i] == 0 || ans[i-s[j]]+1 < ans[i]) ans[i] = ans[i-s[j]]+1; } } cout<<ans[n]<<endl; return 0; } ~~~ ### 16-2 最小化平均结束时间的调度 a)每当一个任务执行完时,就选则剩下的任务中选择执行时间最短的任务执行 b)每当一个任务执行完时,就选则剩下的任务中选择剩余执行时间最短的任务执行,每当一个新的任务到来时,如果它的执行时间比当前任务的剩余执行时间要短,就抢占
';