一、算法思想

貪心就是把整個問題分解成多個步驟，在每個步驟中選取當前步驟的最優方案，直到所有步驟結束。其中每一步都不考慮對后續步驟的影響，后續步驟也不考慮前面步驟的選擇，在特定規則下能夠使局部最優達到全局最優，或者近似全局最優。這就是貪心思想。

二、貪心法的性質

1.最優子結構性質。當一個問題的最優解包含子問題的最優解時，這種情況下就稱滿足最優子結構性質，能從局部最優達到全局最優。

2.貪心選擇性質。問題的全局最優解可以由局部最優解所得到。

三、求解過程

1.將具體問題抽象成數學模型，并選擇合適的貪心策略；

2.將要求解的問題分成若干個子問題；

3.尋求每個子問題的局部最優解；

4.將局部最優解整合得到全局最優解。

四、簡單問題

1.活動安排問題（區間調度問題）

有若干個電視節目，給出它們放映的起止時間，其中有些節目時間會發生沖突，問能完整看完的電視節目最多有多少個？

根據題目所給的條件，有三種貪心策略可供選擇：

（1）最早開始時間；（2）最早結束時間；（3）放映最短時間。

通過簡單的分析判斷可知，（1）和（3）的策略都是不可行的，原因是如果只考慮最早開始時間，而不考慮終止時間，那么會存在最早開始但是最晚結束的情況；如果選擇放映最短時間，那么節目放映的時間點關系就不得而知，無法進行合理判斷。（2）的策略是可行的，按最早結束時間進行排序，就可以安排接下來要看的節目，進而通過判斷條件達到題目的要求。

知道了用什么策略，接下來就是考慮對這個策略的貪心算法步驟：

（1）將 n 個活動按結束時間從小到大進行排序；

（2）選擇第 1 個結束的活動，并排除與它時間沖突的活動；

（3）每次選擇剩下的活動種最早結束的活動再進行（2）的步驟，直到沒有活動可以選擇為止。

再檢查一下以上算法，可以發現它符合貪心算法的性質，大功告成！

AC的C++代碼如下：

#include <iostream> #include <cstring> #include <algorithm>using namespace std; typedef long long ll; const int N = 100 + 5;struct node{ // 定義活動起止時間int start, end; }telecast[N];bool cmp(const node& a, const node& b){ // 結束時間從小到大排序規則return a.end < b.end; }int main() {int n;while(cin >> n && n){for(int i = 0; i < n; i++)cin >> telecast[i].start >> telecast[i].end;sort(telecast, telecast + n, cmp); // 按結束時間從小到大進行排序int cnt = 0;int lastend = -1; // 上一個節目結束時間，初值賦為-1for(int i = 0; i < n; i++){if(telecast[i].start >= lastend){cnt++;lastend = telecast[i].end; // 記錄該活動終止時間，用于下次判斷}}cout << cnt << endl;}return 0; }

例題：hdu2037 今年暑假不AC

2.區間覆蓋問題

農場主John有 N 頭牛，他分配這些牛去打掃圈地衛生（給出每頭牛的工作起止時間），John把一天分成若干個時間段讓牛去打掃，每頭牛打掃的時間是整段時間（不可被分割），你的任務是安排盡量少的牛去完成一天的打掃任務。

根據題意，可以很容易想到，要想安排的牛盡量少，每頭牛工作的時間就得盡量長，因此我們考慮的貪心策略為：每頭牛的工作時間。當然，同時還得考慮上每頭牛的工作開始時間，使得最終的安排充斥整個時間段。開始分析貪心步驟：

（1）把每頭牛的工作時間按起始時間遞增排序；

（2）更新已經覆蓋的區間，再在剩下的牛的工作時間中找到起始時間小于等于區間右端點且終止時間最大的工作時間，再將這個區間加入到已覆蓋的區間；

（3）重復步驟（2），直到區間全部覆蓋。

再檢查一下以上算法，可以發現它符合貪心算法的性質，大功告成！

AC的C++代碼如下：

#include <iostream> #include <cstring> #include <algorithm>using namespace std;const int N = 25000 + 5;struct node{int start, end; }cow[N];bool cmp(const node& a, const node& b){return a.start < b.start; }int main() {int n, t;cin >> n >> t;for(int i = 0; i < n; i++)cin >> cow[i].start >> cow[i].end;sort(cow, cow + n, cmp);cow[n].start = 0x3f3f3f3f;int right = 0, left = 1, flag = 0, cnt = 0;for(int i = 0; i < n; i++){if(cow[i].start <= left){if(cow[i].end > right){right = cow[i].end;flag = 1;}if(cow[i + 1].start > left && flag){left = right + 1;flag = 0;cnt++;}}}if(left - 1 == t) cout << cnt << endl;else cout << -1 << endl;return 0; }

例題：poj2376 Cleaning Shifts

3.最優裝載問題

有 n 種藥水，體積都是 V，濃度不同，把它們混合起來，得到濃度不大于w%的藥水，問怎么混合才能得到最大體積藥水？注意一種藥水要么全用，要么都不用，不能只取一部分。

根據題意，可以很自然想到貪心策略為：找濃度最小的藥水。那么貪心的步驟為：

（1）對藥水濃度按從小到大的順序排序；

（2）循環藥水，并每次對其進行判斷：如果濃度不大于w%就加入，如果大于w%，計算混合后總濃度，不大于w%就加入，否則結束判斷。

再檢查一下以上算法，可以發現它符合貪心算法的性質，大功告成！

AC的C++代碼如下：

#include <iostream> #include <cstring> #include <algorithm> #include <iomanip>using namespace std;const int N = 100 + 5; int liquid[N];int main() {int c, n, v, w;cin >> c;while(c--){cin >> n >> v >> w;for(int i = 0; i < n; i++)cin >> liquid[i];sort(liquid, liquid + n);int vsum = 0;double csum = 0;for(int i = 0; i < n; i++){//if(liquid[i] <= w) csum = (csum * vsum + liquid[i] * v) / (vsum + v); if(csum * vsum + liquid[i] * v <= w * (vsum + v)){csum = (csum * vsum + liquid[i] * v) / (vsum + v);vsum += v;}else break;}if(vsum == 0) cout << 0 << ' ' << "0.00" << endl;else cout << vsum << ' ' << setiosflags(ios::fixed) << setprecision(2) << csum / 100 << endl;}return 0; }

由于不論是藥水濃度小于等于w%還是大于w%，都得更新一次濃度，并且更新濃度的式子是相同的，因此實際代碼中只需判斷加入第 i 瓶藥水后的濃度是否小于w%（可以轉化為物質的量的比較），然后更新即可。

例題：hdu2570 迷瘴

4.多機調度問題

設有 n 個獨立的作業，由 m 臺相同的計算機進行加工。作業 i 的處理時間為?，每個作業可在任何一臺計算機上加工處理，但不能間斷、拆分。要求給出一種作業調度方案，在盡可能短的時間內，由 m 臺計算機加工處理完成這 n 個作業。

多機調度問題是個NP問題，目前無法得到最佳解，只能通過貪心得到最佳解的近似解。

求解該問題的貪心策略是把處理時間最長的作業交給最先空閑的計算機，讓處理時間長的作業優先處理，從而整體獲得盡可能短的處理時間。

該問題有兩種情況：

（1）：需要的時間就是 n 個作業種最長的處理時間 t。

（2）：先將作業按處理時間從大到小排序，再按順序分配給空閑的計算機。

C++代碼如下：

#include <iostream> #include <algorithm> #include <queue>using namespace std; const int M = 1e5 + 5; int a[M];priority_queue<int, vector<int>, greater<int> > q;int main() {int n, m;cin >> n >> m;for(int i = 0; i < m; i++){cin >> a[i];}sort(a, a + m, greater<int>());if(n >= m)cout << a[0] << endl;else{for(int i = 0; i < n; i++){q.push(a[i]);}for(int i = n; i < m; i++){a[i] += q.top();q.pop();q.push(a[i]);}for(int i = 0; i < m - 1; i++)q.pop();cout << q.top() << endl;}return 0; }

五、擴展算法

1.哈夫曼（Huffman）編碼

由于每種字符出現的頻次不同，因此用普通的二進制編碼雖然方便，但不節省空間，這就引出了Huffman編碼的方法。

Huffman編碼是利用貪心思想構造二叉編碼樹的算法。每個二叉樹的分支左邊是0，右邊是1，二叉樹的末端的葉子放編碼，這樣可以保證每個編碼不發生重復。將出現頻次最高的字符放在靠近根的葉子上，編碼最短；將出現頻次最低的字符放在二叉樹最深處的葉子上，編碼最長。這樣就可以實現空間節省的效果，并且能做到每個編碼都不發生重復。

那么接下來的問題就是如何構造這樣的一棵編碼二叉樹：

（1）對所有字符按出現的頻次從小到大進行排序；

（2）從出現頻次最少的字符開始，用貪心思想安排在二叉樹上（每一步都要按頻次重新排序，排序要包括生成的二叉樹的當前根結點），具體步驟如下圖。

可以證明，以上步驟符合貪心法的性質，因此這樣編碼的結果是最優的。

接下來就該考慮代碼如何實現了，我們來看一道例題：

輸入一個字符串，分別用普通ASCII編碼（每個字符8bit）和Huffman編碼，輸出編碼后的長度，并輸出壓縮比。

AC的C++代碼如下：

#include <iostream> #include <algorithm> #include <cstring> #include <iomanip> #include <vector> #include <queue>using namespace std;int main() {string s;priority_queue<int, vector<int>, greater<int> > q; // 優先隊列存儲，頻次最小的在隊首while(cin >> s && s != "END"){int ans1 = 8 * s.size(); // ASCII碼的編碼長度int t = 1;sort(s.begin(), s.end()); // 對字符進行排序int len = s.size();for(int i = 1; i < len; i++){ // 統計各字符出現的次數，并放入優先隊列中if(s[i] != s[i - 1]){q.push(t);t = 1;}else t++;}q.push(t);int ans2 = 0;if(q.size() == 1) ans2 = q.top(); // 字符串只有一個字符的情況while(q.size() > 1){int a = q.top(); // 提取隊列中最小的兩個q.pop();int b = q.top();q.pop();q.push(a + b); // 將當前根結點放回隊列排序ans2 += a + b; // 計算Huffman編碼的總長度}q.pop();cout << ans1 << ' ' << ans2 << ' ' << setiosflags(ios::fixed) << setprecision(1) << (double)ans1 / ans2 << endl;}return 0; }

例題：poj1521 Entropy

2.模擬退火

模擬退火算法基于物理原理：高溫物體降溫的情況是溫度越高降溫越快，溫度越低降溫越慢。基于這種思想，進行多次降溫迭代，直到獲得可行解（無法得到精確解）。

迭代過程中，選擇下一個狀態有兩種可能：
（1）新狀態比原狀態更優，那么接受新狀態；

（2）新狀態比原狀態更差，那么以一定概率接受新狀態，這個概率隨迭代次數逐漸降低。

因此模擬退火算法的步驟如下：

（1）設置初始溫度T、降溫系數Δ和終止溫度eps；

（2）每次迭代溫度按降溫系數下降，以新的溫度計算當前狀態；

（3）溫度降到設定的終止溫度時，迭代停止。

我們來看道典型應用——求函數最值問題：

函數。輸入y值，求函數的最小值。

AC的C++代碼如下：

#include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <cstdlib> #include <iomanip>using namespace std; const double eps = 1e-8; // 終止溫度 double y; // 函數值double cal(double x){return 6 * pow(x, 7.0) + 8 * pow(x, 6.0) + 7 * pow(x, 3.0) + 5 * pow(x, 2.0) - y * x; }double anneal(){double T = 100; // 初始溫度double delta = 0.98; // 降溫系數double x = 50.0; // x的初始值double now = cal(x); // 計算初始函數值double ans = now;while(T > eps){int f[2] = {1, -1};double newx = x + f[rand() % 2] * T; // 按溫度概率改變x的值，概率隨溫度降低而降低if(newx >= 0 && newx <= 100){double next = cal(newx);ans = min(ans, next);if(now - next > eps){x = newx;now = next;}}T *= delta;}return ans; }int main() {int t;cin >> t;while(t--){cin >> y;cout << setiosflags(ios::fixed) << setprecision(4) << anneal() << endl;}return 0; }

例題：hdu2899 Strange function

總結

以上是生活随笔為你收集整理的基础算法思想之贪心法的全部內容，希望文章能夠幫你解決所遇到的問題。

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