算法設計與分析-----貪心法(c語言）

• • 一、貪心法
  • • 1、定義
    • 2、貪心法具有的性質
    • • 1、貪心選擇性質
      • 2、最優子結構性質
    • 3、貪心法的算法框架
    • 5、求解活動安排問題
    • 6、求解最優裝載問題
  • 二、 貪心法實驗
  • • 1、實驗一 求解田忌賽馬問題
    • 2、實驗二 求解多機調度問題
    • 3、實驗三 哈夫曼編碼

一、貪心法

1、定義

? 貪心法的基本思路是在對問題求解時總是做出在當前看來是最好的選擇，也就是說貪心法不從整體最優上加以考慮，所做出的僅是在某種意義上的局部最優解。

? 人們通常希望找到整體最優解，所以采用貪心法需要證明設計的算法確實是整體最優解或求解了它要解決的問題。

2、貪心法具有的性質

1、貪心選擇性質

? 所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。

也就是說，貪心法僅在當前狀態下做出最好選擇，即局部最優選擇，然后再去求解做出這個選擇后產生的相應子問題的解。

2、最優子結構性質

? 如果一個問題的最優解包含其子問題的最優解，則稱此問題具有最優子結構性質。

? 問題的最優子結構性質是該問題可用動態規劃算法或貪心法求解的關鍵特征。

3、貪心法的算法框架

SolutionType Greedy(SType a[],int n) //假設解向量(x0,x1,…,xn-1)類型為SolutionType，其分量為SType類型 { SolutionType x={}； //初始時，解向量不包含任何分量for (int i=0;i<n;i++) //執行n步操作{ SType xi=Select(a); //從輸入a中選擇一個當前最好的分量if (Feasiable(xi)) //判斷xi是否包含在當前解中solution=Union(x,xi); //將xi分量合并形成x }return x; //返回生成的最優解 }

5、求解活動安排問題

? 【問題描述】假設有一個需要使用某一資源的n個活動所組成的集合S，S={1，…，n}。該資源任何時刻只能被一個活動所占用，活動i有一個開始時間bi和結束時間ei（bi<ei），其執行時間為ei-bi，假設最早活動執行時間為0。

? 一旦某個活動開始執行，中間不能被打斷，直到其執行完畢。若活動i和活動j有bi≥ej或bj≥ei，則稱這兩個活動兼容。

? 設計算法求一種最優活動安排方案，使得所有安排的活動個數最多。

? 【問題求解】假設活動時間的參考原點為0。一個活動i（1≤i≤n）用一個區間[bi，ei)表示，當活動按結束時間（右端點）遞增排序后，兩個活動[bi，ei)和[bj，ej)兼容（滿足bi≥ej或bj≥ei）實際上就是指它們不相交。

? 用數組A存放所有的活動，A[i].b（1≤i≤n），存放活動起始時間，A[i].e存放活動結束時間。

i1234567891011

開始時間	1	3	0	5	3	5	6	8	8	2	12
結束時間	4	5	6	7	8	9	10	11	12	13	15

產生最大兼容活動集合的過程：

活動1 √

活動2 ′

活動3 ′

活動4 √

活動5 ′

活動6 ′

活動7 ′

活動8 √

活動9 ′

活動10 ′

活動11 √

代碼如下：

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define MAX 51struct Action { int b; //活動起始時間int e; //活動結束時間bool operator<(const Action &s) const //重載<關系函數{return e<=s.e; //用于按活動結束時間遞增排序} }; int n=11; Action A[]={{0},{1,4},{3,5},{0,6},{5,7},{3,8},{5,9},{6,10},{8,11},{8,12},{2,13},{12,15}}; //下標0不用 //求解結果表示 bool flag[MAX]; //標記選擇的活動 int Count=0; //選取的兼容活動個數 void solve() //求解最大兼容活動子集 {memset(flag,0,sizeof(flag));//初始化為falsesort(A+1,A+n+1); //A[1..n]按活動結束時間遞增排序int preend=0; //前一個兼容活動的結束時間for (int i=1;i<=n;i++){ if (A[i].b>=preend){ flag[i]=true; //選擇A[i]活動preend=A[i].e;}} } int main() {solve();printf("求解結果\n");printf(" 選取的活動:");for (int i=1;i<=n;i++)if (flag[i]){printf("[%d,%d] ",A[i].b,A[i].e);Count++;}printf("\n 共%d個活動\n",Count); }

【算法分析】算法的主要時間花費在排序上，排序時間為O(nlog2n)，所以整個算法的時間復雜度為O(nlog2n)。

6、求解最優裝載問題

【問題描述】有n個集裝箱要裝上一艘載重量為W的輪船，其中集裝箱i（1≤i≤n）的重量為wi。

? 不考慮集裝箱的體積限制，現要選出盡可能多的集裝箱裝上輪船，使它們的重量之和不超過W。

【問題求解】第5章討論了簡單裝載問題，采用回溯法選出盡可能少的集裝箱個數。這里的最優解是選出盡可能多的集裝箱個數，并采用貪心法求解。

? 當重量限制為W時，wi越小可裝載的集裝箱個數越多，所以采用優先選取重量輕的集裝箱裝船的貪心思路。

? 對wi從小到大排序得到{w1，w2，…，wn}，設最優解向量為x={x1，x2，…，xn}，顯然，x1=1，則x’={x2，…，xn}是裝載問題w’={w2，…，wn}，W’=W-w1的最優解，滿足貪心最優子結構性質。

代碼如下：

#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define MAXN 20 //最多集裝箱個數int w[]={0,5,2,6,4,3}; //各集裝箱重量,不用下標0的元素 int n=5,W=10;int maxw; //存放最優解的總重量 int x[MAXN]; //存放最優解向量void solve() //求解最優裝載問題 {memset(x,0,sizeof(x)); //初始化解向量sort(w+1,w+n+1); //w[1..n]遞增排序maxw=0;int restw=W; //剩余重量for (int i=1;i<=n && w[i]<=restw;i++){x[i]=1; //選擇集裝箱irestw-=w[i]; //減少剩余重量maxw+=w[i]; //累計裝載總重量} } int main() {solve();printf("最優方案\n");for (int i=1;i<=n;i++)if (x[i]==1)printf(" 選取重量為%d的集裝箱\n",w[i]);printf("總重量=%d\n",maxw); }

【算法分析】算法的主要時間花費在排序上，時間復雜度為O(nlog2n)。

二、 貪心法實驗

1、實驗一 求解田忌賽馬問題

? 【問題描述】二千多年前的戰國時期，齊威王與大將田忌賽馬。雙方約定每人各出300匹馬，并且在上、中、下三個等級中各選一匹進行比賽，由于齊威王每個等級的馬都比田忌的馬略強，比賽的結果可想而知。現在雙方各n匹馬，依次派出一匹馬進行比賽，每一輪獲勝的一方將從輸的一方得到200銀幣，平局則不用出錢，田忌已知所有馬的速度值并可以安排出場順序，問他如何安排比賽獲得的銀幣最多。

? 輸入：輸入包含多個測試用例，每個測試用例的第一行正整數n（n≤1000）馬的數量，后兩行分別是n個整數，表示田忌和齊威王的馬的速度值。輸入n=0結束。

? 輸出：每個測試用例輸出一行，表示田忌獲得的最多銀幣數。

輸入樣例：

3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0

樣例輸出：

200 0 0

【問題求解】田忌的馬速度用數組a表示，齊威王的馬速度用數組b表示，將a、b數組遞增排序。采用常識性的貪心思路，分以下幾種情況：

（1）田忌最快的馬比齊威王最快的馬快即a[righta]>b[rightb]，則兩者比賽（兩個最快的馬比賽），田忌贏。因為此時田忌最快的馬一定贏，而選擇與齊威王最快的馬比賽對于田忌來說是最優的，下圖中“■”代表已經比賽的馬，“□”代表尚未比賽的馬，箭頭指向的馬速度更快。

（2）田忌最快的馬比齊威王最快的馬慢即a[righta]<b[rightb]，則選擇田忌最慢的馬與齊威王最快的馬比賽，田忌輸。因為齊威王最快的馬一定贏，而選擇與田忌最慢的馬比賽對于田忌來說是最優的。

（3）田忌最快的馬與齊威王最快的馬的速度相同即a[righta]=b[rightb]，又分為以下3種情況：

? ① 田忌最慢的馬比齊威王最慢的馬快即a[lefta]>b[leftb]，則兩者比賽（兩個最慢的馬比賽），田忌贏。因為此時齊威王最慢的馬一定輸，而選擇與田忌最慢的馬比賽對于田忌來說是最優的。

? ② 田忌最慢的馬比齊威王最慢的馬慢，并且田忌最慢的馬比齊威王最快的馬慢，即a[lefta]≤b[leftb]且a[lefta]<b[rightb]，則選擇田忌最慢的馬與齊威王最快的馬比賽，田忌輸。因為此時田忌最慢的馬一定輸，而選擇與齊威王最快的馬比賽對于田忌來說是最優的。

? ③ 其他情況，即a[righta]=b[rightb]且a[lefta]≤b[leftb]且a[lefta]≥b[rightb]，則a[lefta]≥b[rightb]=a[righta]，即a[lefta]=a[righta]，b[leftb]≥a[lefta]=b[rightb]，即b[leftb]=b[rightb]，說明比賽區間的所以馬的速度全部相同，任何兩匹馬比賽都沒有輸贏。

上述過程看出每種情況對于田忌來說都是最優的，因此最終獲得的比賽方案也一定是最優的。

代碼如下：

#include <stdio.h> #include <algorithm> using namespace std; #define MAX 1001int n; int a[MAX]; int b[MAX];int ans; void solve() //求解算法 {sort(a,a+n); //對a遞增排序sort(b,b+n); //對b遞增排序ans=0;int lefta=0,leftb=0;int righta=n-1,rightb=n-1;while (lefta<=righta) //比賽直到結束{if (a[righta]>b[rightb]) //田忌最快的馬比齊威王最快的馬快，兩者比賽{ans+=200;righta--;rightb--;}else if (a[righta]<b[rightb]) //田忌最快的馬比齊威王最快的馬慢，選擇田忌最慢的馬與比齊威王最快的馬比賽{ans-=200;lefta++;rightb--;}else //田忌最快的馬與齊威王最快的馬的速度相同{if (a[lefta]>b[leftb]) //田忌最慢的馬比齊威王最慢的馬快，兩者比賽{ans+=200;lefta++;leftb++;}else{if (a[lefta]<b[rightb]) //否則，用田忌最慢的馬與齊威王最快的馬比賽ans-=200;lefta++;rightb--;}}} } int main() {while (true){scanf("%d",&n);if (n==0) break;for (int i=0;i<n;i++)scanf("%d",&a[i]);for (int j=0;j<n;j++)scanf("%d",&b[j]);solve();printf("%d\n",ans);}return 0; }

【算法分析】算法的主要時間花費在排序上，時間復雜度為O(nlog2n)。

2、實驗二 求解多機調度問題

【問題描述】設有n個獨立的作業{1，2，…，n}，由m臺相同的機器{1，2， …，m}進行加工處理，作業i所需的處理時間為ti（1≤i≤n），每個作業均可在任何一臺機器上加工處理，但未完工前不允許中斷，任何作業也不能拆分成更小的子作業。

多機調度問題要求給出一種作業調度方案，使所給的n個作業在盡可能短的時間內由m臺機器加工處理完成。

【問題求解】貪心法求解多機調度問題的貪心策略是最長處理時間作業優先，即把處理時間最長的作業分配給最先空閑的機器，這樣可以保證處理時間長的作業優先處理，從而在整體上獲得盡可能短的處理時間。

按照最長處理時間作業優先的貪心策略，當m≥n時，只要將機器i的[0，ti)時間區間分配給作業i即可；

當m<n時，首先將n個作業依其所需的處理時間從大到小排序，然后依此順序將作業分配給空閑的處理機。

例如，有7個獨立的作業{1，2，3，4，5，6，7}，由3臺機器{1，2，3}加工處理，各作業所需的處理時間如下：

作業編號1234567

作業的處理時間	2	14	4	16	6	5	3

采用貪心法求解的過程如下：

（1）7個作業按處理時間遞減排序，其結果如下表所示。

作業編號4256371

作業的處理時間	16	14	6	5	4	3	2

（2）先將排序后的前3個作業分配給3臺機器。此時機器的分配情況為{{4}，{2}，{5}}，對應的總處理時間為{16，14，6}。

作業編號4256371

作業的處理時間	16	14	6	5	4	3	2

（3）分配余下的作業

代碼如下：

#include <stdio.h> #include <queue> #include <vector> #include <algorithm> using namespace std; #define N 100int n=7; int m=3; struct NodeType {int no; //作業序號int t; //執行時間int mno; //機器序號bool operator<(const NodeType &s) const { return t>s.t; } //按t越小越優先出隊 }; struct NodeType A[]={{1,2},{2,14},{3,4},{4,16},{5,6},{6,5},{7,3}}; void solve() //求解多機調度問題 {NodeType e;if (n<=m){ printf("為每一個作業分配一臺機器\n");return;}printf(" 排序前");for (int s=0;s<n;s++)printf(" [%d:%d]",A[s].no,A[s].t);printf("\n");sort(A,A+n);printf(" 排序后");for (int s=0;s<n;s++)printf(" [%d:%d]",A[s].no,A[s].t);printf("\n");priority_queue<NodeType> qu; //小根堆for (int i=0;i<m;i++){A[i].mno=i+1;printf(" 給機器%d分配作業%d,執行時間為%2d,占用時間段:[%d,%d]\n",A[i].mno,A[i].no,A[i].t,0,A[i].t);qu.push(A[i]);}for (int j=m;j<n;j++){e=qu.top(); qu.pop(); //出隊eprintf(" 出隊:e.no=%d,e.t=%d,e.mno=%d\n",e.no,e.t,e.mno); printf(" 給機器%d分配作業%d,執行時間為%2d,占用時間段:[%d,%d]\n",e.mno,A[j].no,A[j].t,e.t,e.t+A[j].t);e.t+=A[j].t;qu.push(e); //e進隊printf(" 進隊:e.no=%d,e.t=%d,e.mno=%d\n",e.no,e.t,e.mno); } } int main() {printf("多機調度方案:\n");solve(); }

【算法分析】排序的時間復雜度為O(nlog2n)，兩次for循環的時間合起來為O(n)，所以本算法的時間復雜度為O(nlog2n)。

3、實驗三 哈夫曼編碼

【問題描述】設要編碼的字符集為{d1， d2， …， dn}，它們出現的頻率為{w1， w2， …， wn}，應用哈夫曼樹構造最優的不等長的由0、1構成的編碼方案。

【問題求解】先構建以這個n個結點為葉子結點的哈夫曼樹，然后由哈夫曼樹產生各葉子結點對應字符的哈夫曼編碼。

? 哈夫曼樹（Huffman Tree）的定義：設二叉樹具有n個帶權值的葉子結點，從根結點到每個葉子結點都有一個路徑長度。從根結點到各個葉子結點的路徑長度與相應結點權值的乘積的和稱為該二叉樹的帶權路徑長度，記作：

? 由n個葉子結點可以構造出多種二叉樹，其中具有最小帶權路徑長度的二叉樹稱為哈夫曼樹（也稱最優樹）。

構造一棵哈夫曼樹的方法如下：

（1）由給定的n個權值{w1，w2，…，wn}構造n棵只有一個葉子結點的二叉樹，從而得到一個二叉樹的集合F={T1，T2，…，Tn}。

（2）在F中選取根結點的權值最小和次小的兩棵二叉樹作為左、右子樹構造一棵新的二叉樹，這棵新的二叉樹根結點的權值為其左、右子樹根結點權值之和。即合并兩棵二叉樹為一棵二叉樹。

（3）重復步驟（2），當F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。

代碼如下：

#include <iostream> #include <queue> #include <vector> #include <string> #include <map> using namespace std; #define MAX 101 int n; struct HTreeNode //哈夫曼樹結點類型 {char data; //字符int weight; //權值int parent; //雙親的位置int lchild; //左孩子的位置int rchild; //右孩子的位置 }; HTreeNode ht[MAX]; //哈夫曼樹 map<char,string> htcode; //哈夫曼編碼struct NodeType //優先隊列結點類型 {int no; //對應哈夫曼樹ht中的位置char data; //字符int weight; //權值bool operator<(const NodeType &s) const{ //用于創建小根堆return s.weight<weight;} }; void CreateHTree() //構造哈夫曼樹 {NodeType e,e1,e2;priority_queue<NodeType> qu;for (int k=0;k<2*n-1;k++) //設置所有結點的指針域ht[k].lchild=ht[k].rchild=ht[k].parent=-1;for (int i=0;i<n;i++) //將n個結點進隊qu{e.no=i;e.data=ht[i].data;e.weight=ht[i].weight;qu.push(e);}for (int j=n;j<2*n-1;j++) //構造哈夫曼樹的n-1個非葉結點{e1=qu.top(); qu.pop(); //出隊權值最小的結點e1e2=qu.top(); qu.pop(); //出隊權值次小的結點e2ht[j].weight=e1.weight+e2.weight; //構造哈夫曼樹的非葉結點j ht[j].lchild=e1.no;ht[j].rchild=e2.no;ht[e1.no].parent=j; //修改e1.no的雙親為結點jht[e2.no].parent=j; //修改e2.no的雙親為結點je.no=j; //構造隊列結點ee.weight=e1.weight+e2.weight;qu.push(e);} } void CreateHCode() //構造哈夫曼編碼 {string code;code.reserve(MAX);for (int i=0;i<n;i++) //構造葉結點i的哈夫曼編碼{code="";int curno=i;int f=ht[curno].parent;while (f!=-1) //循環到根結點{if (ht[f].lchild==curno) //curno為雙親f的左孩子code='0'+code;else //curno為雙親f的右孩子code='1'+code;curno=f; f=ht[curno].parent;}htcode[ht[i].data]=code; //得到ht[i].data字符的哈夫曼編碼} } void DispHCode() //輸出哈夫曼編碼 {map<char,string>::iterator it;for (it=htcode.begin();it!=htcode.end();++it)cout << " " << it->first << ": " << it->second << endl; } void DispHTree() //輸出哈夫曼樹 {for (int i=0;i<2*n-1;i++){printf(" data=%c, weight=%d, lchild=%d, rchild=%d, parent=%d\n",ht[i].data,ht[i].weight,ht[i].lchild,ht[i].rchild,ht[i].parent);} } int WPL() //求WPL {int wps=0;for (int i=0;i<n;i++)wps+=ht[i].weight*htcode[ht[i].data].size();return wps; }int main() {n=5;ht[0].data='a'; ht[0].weight=4; //置初值即n個葉子結點ht[1].data='b'; ht[1].weight=2; ht[2].data='c'; ht[2].weight=1; ht[3].data='d'; ht[3].weight=7; ht[4].data='e'; ht[4].weight=3; CreateHTree(); //建立哈夫曼樹printf("構造的哈夫曼樹:\n");DispHTree();CreateHCode(); //求哈夫曼編碼printf("產生的哈夫曼編碼如下:\n");DispHCode(); //輸出哈夫曼編碼printf("WPL=%d\n",WPL()); }

總結

以上是生活随笔為你收集整理的算法设计与分析-----贪心法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。