一、貪心算法

解決最優化問題的算法一般包含一系列的步驟，每一步都有若干的選擇。對于很多最優化問題，只需要采用簡單的貪心算法就可以解決，而不需要采用動態規劃方法。貪心算法使所做的局部選擇看起來都是當前最佳的，通過局部的最優化選擇來產生全局最優解。本文將介紹貪心算法的理論基礎和一些簡單應用。在求最優解問題的過程中，依據某種貪心標準，從問題的初始狀態出發，直接去求每一步的最優解，通過若干次的貪心選擇，最終得出整個問題的最優解，這種求解方法就是貪心算法。

設計貪心算法的步驟：

將最優化問題轉化為這樣一個問題，即先做出選擇，再解決剩下的一個子問題。
證明原問題的最優解之一可以由貪心選擇得到。
證明在做出貪心選擇后，將剩余的子問題的最優解和我們所做的貪心選擇組合起來，可以得到原問題的一個最優解。
一般，如果我們能證明一個問題具有以下兩個關鍵的性質，那么就可以設計出它的一個貪心算法。

（1）貪心選擇性質：一個全局最優解可以通過局部最優解（貪心）選擇來達到。即，當考慮做選擇時，只考慮對當前問題最佳的選擇而不考慮子問題的結果。而在動態規劃中，每一步都要做出選擇，這些選擇依賴于子問題的解。動態規劃一般是自底向上，從小問題到大問題。貪心算法通常是自上而下，一個一個地做貪心選擇，不斷地將給定的問題實例規約為更小的子問題。
（2）含有最優子結構： 如果問題的一個最優解包含了其子問題的最優解，則稱該問題具有最優子結構。**

利用貪心解決問題的關鍵需要考慮如何選取貪心標準。
貪心算法的理論基礎
關于貪心算法有一種理論可用于確定在何時使用貪心算法能給出最優解，雖然這種理論并沒有包含貪心算法所適用的所有情況，但確實描述了許多非常有意義的情況。

二、適用題型

1.活動選擇問題。

這層樓沿著走廊南北向的兩邊各有200個房間。最近，公司要做一次裝修，需要在各個辦公室之間搬運辦公桌。由于走廊狹窄，辦公桌都很大，走廊里一次只能通過一張辦公桌。必須制定計劃提高搬運效率。經理制定如下計劃：一張辦公桌從一個房間移到另一個房間最多用十分鐘。當從房間i移動一張辦公桌到房間j，兩個辦公室之間的走廊都會被占用。所以，每10分鐘內，只要不是同一段走廊，都可以在房間之間移動辦公桌。

思路如果搬運桌子的路徑有重疊，那么必定不能夠同時進行，所以考慮每個房間經過的次數即為搬運的最短情況。

int i, j; int move[200]; int N;　　　　　　　　//搬運次數 //每次搬運的起點和終點 int from, to; scanf("%d", &N); memset(move, 0, sizeof(move)); for(i = 0; i < N; i++) {scanf("%d%d", &from, &to);//將房間號映射為走廊號from = (from - 1)/2;to = (to - 1)/2;//確保from<to，C++使用：swap(from, to)if(from > to) {int temp = from; from = to; to = temp;}//占用走廊情況for(j = from; j <= to; j++)move[j]++; }

2.可拆分背包問題

選出貪心準則，按照符合題意程度優先的順序選擇。
例如，去自助餐廳吃飯，要想吃回本就要撿著貴的吃，但是貴只是一方面，人會飽，所以用價格除以質量所獲的價格商才是貪心準則，應按照價格商優先進行選取。

3.最優裝載問題

有一批集裝箱要裝上一艘載重量為c的輪船，其中集裝箱i的重量為wi。最優裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。

既然體積不受限制，只受質量限制，那可知從質量小的集裝箱開始選取。

4.刪數問題

string a;　　　　　　　　//n位數a int k; cin>>a>>k; //如果k≥n，數字被刪完了 If (k >= a.size()) a.erase(); else while(k > 0) {//尋找最近下降點int i;for (i=0; (i<a.size()-1) && (a[i] <= a[i+1]); ++i);a.erase(i, 1);　　　　//刪除xik- -; } //刪除前導數字0 while(a.size() > 1 && a[0] == '0') a.erase(0, 1); cout<<a<<endl;

5.多處最優服務次序問題

本題想讓客戶等待時間短，那如果讓時間長的在前，就會有所用人等候最長時間人情況出現，肯定不為最優解。假設從最小的開始，人的基數乘以時間是一個小量，然后事間逐漸延長，人數減少。

6.多機調度問題

n個作業組成的作業集，可由m臺相同機器加工處理。要求給出一種作業調度方案，使所給的n個作業在盡可能短的時間內由m臺機器加工處理完成。作業不能拆分成更小的子作業；每個作業均可在任何一臺機器上加工處理。這個問題是NP完全問題，還沒有有效的解法(求最優解)，但是可以用貪心選擇策略設計出較好的近似算法(求次優解)。當n<=m時，只要將作業時間區間分配給作業即可；當n>m時，首先將n個作業從大到小排序，然后依此順序將作業分配給空閑的處理機。也就是說從剩下的作業中，選擇需要處理時間最長的，然后依次選擇處理時間次長的，直到所有的作業全部處理完畢，或者機器不能再處理其他作業為止。如果我們每次是將需要處理時間最短的作業分配給空閑的機器，那么可能就會出現其它所有作業都處理完了只剩所需時間最長的作業在處理的情況，這樣勢必效率較低。

7.區間覆蓋問題

POJ1328是一道經典的貪心算法例題。題目大意是假設海岸線是一條無限延伸的直線。陸地在海岸線的一側，而海洋在另一側。每一個小的島嶼是海洋上的一個點。雷達坐落于海岸線上，只能覆蓋d距離，所以如果小島能夠被覆蓋到的話，它們之間的距離最多為d。題目要求計算出能夠覆蓋給出的所有島嶼的最少雷達數目。對于每個小島，我們可以計算出一個雷達所在位置的區間。

問題轉化為如何用盡可能少的點覆蓋這些區間。先將所有區間按照左端點大小排序，初始時需要一個點。如果兩個區間相交而不重合，我們什么都不需要做；如果一個區間完全包含于另外一個區間，我們需要更新區間的右端點；如果兩個區間不相交，我們需要增加點并更新右端點.

總結

以上是生活随笔為你收集整理的疯子的算法总结(四）贪心算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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