第16章貪心算法 · 《算法導論》答案

# 一、綜述貪心算法是使所做的選擇看起來都是當前最佳的，期望通過所做的局部最優選擇來產生出一個全局最優解最小生成樹算法是貪心算法的一個經典的例子 # 二、活動選擇問題 ### （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）每當一個任務執行完時，就選則剩下的任務中選擇剩余執行時間最短的任務執行，每當一個新的任務到來時，如果它的執行時間比當前任務的剩余執行時間要短，就搶占