原文

https://bbs.fmcraft.top/blog/index.php/archives/22/

貪心算法

概述

近年來的信息學競賽試題，經常出現求一個問題的可行解或最優解的題目。這類問題就是我們通常所說的最優化問題。貪心算法是求解這類問題的一種常用算法。在眾多的算法中，貪心算法可以算得上是最接近人們日常思維的一種算法，常被信息學奧賽選手用來求解一些數據規模很大的問題。

一、貪心算法

貪心算法是從問題的初始狀態出發，通過若干次的貪心選擇而得到的最優值(或較優值)的一種求解問題策略，即貪心策略。
換句話說，貪心策略是一種在每次決策時采取當前意義下最優策略的算法，做出的選擇只是在某種約束條件下的局部最優解或較優解，并不一定是全局的最優解或較優解。不過，某些特定的問題是可以利用貪心算法求得其最優解或較優解的。
【引例1】在N行M列的正整數矩陣中，要求從每行中選出一個數，使得選出的N個數的和最大。
分析：本題可以用貪心算法求解。選N次，每一次選出相應行中的最大值即可。
【引例2】在一個N×M的方格陣中，每一格子賦予一個數(即權值),規定每次移動時只能向上或向右。現試找出一條路徑，使其從左下角至右上角所經過的權值之和最大。
我們以2×3的矩陣為例：

/	列1	列2	列3
行1	3	4	6
行2	1	2	10
若按貪心算法求解，所得路徑為：1→3→4→6。
若按動態規劃求解，所得路徑為：1→2→ 10→6。
顯然，這里用貪心算法求解，得到的并不是問題的最優解。

二、貪心算法的特點

1.貪心選擇

所謂貪心選擇是指應用同一規則，將原問題變為一個相似的但規模更小的子問題，而后的每 一步都是當前看似最佳的選擇，且這種選擇只依賴于已做出的選擇，不依賴于未做出的選擇。

最優子結構

執行算法時，每一次得到的結果雖然都是當前問題的最優解(即局部最優解),但只有滿足全 局最優解包含局部最優解時，才能保證最終得到的結果是最優解。

三、幾個簡單的貪心實例

1.最優裝載問題

給 n 個物體，第i個物體重量為W?, 選擇盡量多的物體，使得總重量不超過C。
【思路點撥】
由于只關心物體的數量，所以裝重的沒有裝輕的劃算。只需把所有物體按重量從小到大排 序，依次選擇每個物體，直到裝不下為止。這就是一種典型的貪心算法，它只顧眼前，但卻能得到全 局最優解。
貪心策略：先裝最輕的。

2.部分背包問題

有n 個物體，第i個物體的重量為w?, 價值為 v?,在總重量不超過C 的情況下讓總價值盡量高。 每一個物體可以只取走一部分，價值和重量按比例計算。
【思路點撥】
本題是在上一題的基礎上增加了價值項，所以不能簡單地像上一題那樣先選出輕的(輕的可 能其價值也小),也不能先拿價值大的(它可能特別重),而應該綜合考慮兩個因素。一種直觀的貪心策略是：優先選出價值與重量的比值最大的，直到重量和正好為C。
注意：由于每個物體可以只選出一部分，因此一定可以讓總重量恰好為C(或者所有物體全選，總重量還不足C), 而且除了最后一個以外，所有的物體要么不選，要么全部選。
貪心策略：先選出性價比高的。

3.乘船問題

有n個人，第i個人重量為w,。每艘船的載重量均為C,最多可乘兩個人。求用最少的船裝載所有人的方案。
【思路點撥】
考慮最輕的人i, 他應該和誰一起乘呢?如果每個人都不能和他一起乘，則只能每人乘一艘船。 否則，他應該選擇能和他一起乘的人中最重的一個人j。這樣的選擇只是讓“眼前”的浪費最少，因此它是一種貪心策略。
貪心策略：最輕的人和最重的人配對。
這個貪心策略的正確性和有效性是可以用反證法證明的。
證明：假設這個貪心策略不是最優的，最優方案中的i是什么樣的呢?
情況1:i不和任何一個人乘同一艘船，那么可以把j拉過來和他一起乘，總船數不會增加(且可能會減少!),并且符合貪心策略。
情況2:i和另外一個人k同乘一艘船，其中k比j輕。把j和k交換后，j原來所在的船仍然不會超重(因為k比j輕),因此i和j同乘一艘船，所得到的新解不會更差，且符合貪心策略。
由此可見，利用本題的貪心策略求解不會丟失最優解。
程序實現。在前面的分析中，比j更重的人只能每人乘一艘船。這樣，我們只需用兩個指針i和j分別表示當前考慮的最輕的人和最重的人。每次先將指針j往左移動，直到i和j可以共乘一艘船，然后將指針i往右移，指針j往左移，并重復上述操作，直到所有的人都裝載上。不難看出，這 個程序的時間復雜度僅為O(n), 是最優算法。

總結

通過以上3個例子，我們大致了解了貪心算法的形式和正確性證明的基本方法。下面，進一步分析幾個經典貪心算法的應用，加深對貪心算法的理解。

四、貪心算法的經典應用

1.選擇不相交區間問題

給定n個開區間(a,b),選擇盡量多個區間，使得這些區間兩兩沒有公共點。
【思路點撥】
首先，按照b_1<=b_2<=…<=b_n,的順序排序，依次考慮各個區間，如果沒有和已經選擇的區間沖突，就選：否則就不選。
【正確性】
假設b_1＜b_i且(a_j,b_j)、(a_i,b_i) 分別與之前的區間不沖突，當前選(a_j,b_j).若(a_j,b_j)與(a_j,b_i)不沖突，則還可以選擇(a_i,b_i),答案個數加一；若(a_j,b_j)與(a_i,b_i)沖突，因為b_j＜b_i,所以選(a_j,b_j)對以后的影響更小。

2.區間選點問題

【問題描述】
給定n個閉區間[a_i,b_i], 在數軸上選盡量少的點，使得每個區間內都至少有一個點(不同區同內含的點可以是同一個)。
【思路點撥】
首先按照區間的結束位置從小到大排序。然后從區間1到區間n 進行選擇：對于當前區間，吾 集合中的數不能覆蓋它，則將區間末尾的數加入集合。
貪心策略：取最后一個。
如圖下圖所示，如果選灰色點，則移動到黑色點會更優。

3.區間覆蓋問題

【問題描述】
給n個閉區間[a_i,b_i],選擇盡量少的區間覆蓋一條指定的線段區間[s,t]。
【思路點撥】
將所有的區間按左端點從小到大排序，依次處理每個區間。每次選擇覆蓋點s的區間中右端 點坐標最大的一個，并將s更新為該區間的右端點坐標，直到選擇的區間已包含了t為止。
貪心策略：在某個時刻的s, 找一個滿足a[i]≤s的b[i]最大值即可。

4.流水作業調度問題

【問題描述】
有n個作業要在兩臺機器M1和M2組成的流水線上完成加工。每個作業i都必須先花時間a在M上加工，然后花時間b在M2上加工。
確定n個作業的加工順序，使得從作業1在機器M1上加工開始到作業n在機器M2上加工實完為止所用的總時間最短。
【思路點撥】
直觀上，最優調度一定讓M1、M2的空閑時間盡量短。
Johnson算法：設N1為a＜b的作業集合，N2 為a≥b的作業集合，將N1的作業按a非減序排序，N2中的作業按照b非增序排序，則N1作 業接N2作業構成最優順序。
算法的程序易于實現，時間復雜度為O(nlogn),正確性需要證明。

5.帶限期和罰款的單位時間任務調度

【問題描述】
有n個任務，每個任務都需要1個時間單位執行，任務i的截止時間d_i(1≤d≤n)表示要求任務i在時問d_i結束時必須完成，誤時懲罰w_i表示若任務i未在時間d_i結束之前完成，將導致w_i的罰款。
確定所有任務的執行順序，使得懲罰最少。
【思路點撥】
要使罰款最少.我們顯然應盡量完成w[i]值較大的任務。
此時，我們可以將任務按w[i]從大到小進行排序，然后按照排好的順序依次對任務進行安排。 安排的規則為：使處理任務i的時間既在d[i]之內，又盡量靠后；如果d[i]之內的時間都已經排滿，就放棄處理此項任務。
【算法證明】
假設按照上述算法得到的解不是最優的，那么必然存在某個任務j應當安排到處理的過程中 但卻沒有安排。假設我們要將該任務安排進去，由于在時間d[j]內都已經排滿，就必然需要將一個已安排的任務k與之替換，而w[k]≥w[j]。 這樣，替換顯然會增加罰款的數額、因此，除上還安排方法以外的安排方法都不會使罰款的數額減少，可知用上述算法得到的結果是最優的。
【實現方法】
①先按照罰款數額從大到小快排。
②順序處理每個任務，若能安排，則找一個最晚時間：否則放在最后的空位上。

練習

如需練習學習的內容，可自行尋找相關題目。
也可以前往FMCRAFT OJ做題。下面的地址可以直接跳轉到其相關題目一本通訓練中的題單 算法訓練中的題單。使用OJ前需要注冊賬戶。