貪心算法介紹

接下來的三個小節(jié)內容我們將介紹基礎算法中的一個經典算法：貪心算法。貪心算法比較直觀，有時候能很好的解決問題，但有時候求出的結果非最優(yōu)解。所以在使用貪心算法時一定要對其應用場景以及相應的問題掌握清楚，方能在算法題解中游刃有余。

1. 貪心算法介紹

所謂貪心算法是指在對問題求解時，總是選擇在當前看來是最好的方法。即從局部考察最優(yōu)而非整體。貪心算法沒有固定的算法框架，算法設計的關鍵是貪心策略的選擇。必須注意的是：貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性 （即某個狀態(tài)以后的過程不會影響以前的狀態(tài)，只與當前狀態(tài)有關）。 所以，對所采用的貪心策略一定要仔細分析其是否滿足無后效性。

2. 貪心算法思路介紹

對于貪心算法，其實現(xiàn)思路一般如下：

• 建立數學模型來描述問題；
• 把求解的問題分成若干個子問題；
• 對每個子問題求解，得到子問題的局部最優(yōu)解；
• 把子問題的解局部最優(yōu)解合成原來問題的一個解。

3. 要不要使用貪心算法？

使用貪心算法在很多問題上不一定能求得最優(yōu)解，因此我們再使用貪心算法時需要嚴格思考使用貪心的策略能否達到我們想要的結果。貪心策略適用的前提是：局部最優(yōu)策略能導致產生全局最優(yōu)解。實際上，貪心算法適用的情況很少，一般對一個問題分析是否適用于貪心算法，可以先選擇該問題下的幾個實際數據進行分析，就可以做出判斷。

貪心選擇性質是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即當考慮做何種選擇的時候，我們只考慮對當前問題最佳的選擇而不考慮子問題的結果。這是貪心算法可行的第一個基本要素。貪心算法以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用貪心算法求解的關鍵特征。

在介紹完貪心相關的概念、實現(xiàn)思路、缺陷以及相關適用場景后，我們介紹一個關于貪心算法的典型應用場景，幫助我們更好的理解貪心的實現(xiàn)，便于后面完成相應的題解。

4. 貪心算法的典型應用

這是一個非常經典的編程題，題名為：洞中取寶，題目的描述如下：

假設山洞中有 n 種寶物，每種寶物有一定重量 w 和相應的價值 v，毛驢運載能力有限，只能運走 m 重量的寶物，一種寶物只能拿一樣，寶物可以分割。那么怎么才能使毛驢運走寶物的價值最大呢？

注意：由于寶物有重量和價值兩種特征，我們的貪心是應該取價值還是重量呢？還是二者兼顧？這樣會產生三種貪心策略：

• 每次挑選價值最大的寶物，直到無法運載下一個寶物為止；
• 每次挑選重量最輕的寶物，直到無法運載下一個寶物為止；
• 每次挑選價值/重量 最大的寶物，直到無法運載下一個寶物為止；

很明顯，我們貪心的策略應該選擇第三種，這樣能兼顧寶物價值和重量，找到滿足要求的最優(yōu)解：

• $ts[i]￥：表示第 i 個寶物的價值 $i=1...n$；
• $ws[i]$：表示第 i 個寶物的重量 $i=1...n$；
• $t$：表示毛驢最大運載能力。

此時我們需要計算寶物的單位價值：
$pre\_value[i]=\frac{ts[i]}{ws[i]},i=1,\cdots,n$

5. 貪心算法的 Python 代碼實現(xiàn)

有了寶物的單位價值之后，接下來我們需要對寶物按照單位價值進行排序，使用 python 自帶的 sort 方法即可。注意要保持寶物的價值和總量一起變化，所以需要將寶物的重量、價值以及單位價值作為一個整體，然后進行排序：

pre_value = []
for i in range(len(ts)):
    pre_value.append([ts[i], ws[i], ts[i] / ws[i]])
# 按照單位價值從大到小進行排序
pre_value.sort(key=lambda d: d[2], reverse=True)

接下來就是按照貪心算法從大到小選擇，直到寶物價值超出剩余的運載價值，然后將寶物切割帶走：

for i in range(len(pre_value)):
    if pre_value[i][1] <= t:
        # 從大到小開始裝
        w += pre_value[i][0]
        # 每裝一個運載能力減去寶物重量
        t -= pre_value[i][1]
    else:
        # 可以取走寶物的一部分，達到最大裝載
        w += pre_value[i][2] * t
        break

整體給出洞中取寶問題的貪心實現(xiàn)，如下：

def get_treasures(ts, ws, t):
    """ 
    ts: 寶物價值
    ws: 寶物重量
    t：最大運載能力
    """
    
    w = 0
    # 計算寶物的性價比
    pre_value = []
    for i in range(len(ts)):
        pre_value.append([ts[i], ws[i], ts[i] / ws[i]])
    # 將寶物按單位價值從大到小進行排序
    pre_value.sort(key=lambda d: d[2], reverse=True)
    for i in range(len(pre_value)):
        if pre_value[i][1] <= t:
            w += pre_value[i][0]
            t -= pre_value[i][1]
        else:
            # 可以取走寶物的一部分，達到最大裝載
            w += pre_value[i][2] * t
            break
    return w

if __name__ == '__main__':
    ts = [4, 2, 9, 5, 5, 8, 5, 4, 5, 5]
    ws = [3, 8, 18, 6, 8, 20, 5, 6, 7, 15]

    t = 30

    print("運走寶物的最大價值為:{}".format(get_treasures(ts, ws, t)))

還有許多類似的問題，如背包問題、最優(yōu)裝載問題、教室調度問題等等，都可以使用貪心算法解決。但是我們一定要找對貪心的值，這樣才能確保得到最優(yōu)的解。

6. 小結

本小節(jié)我們主要介紹了貪心算法以及相應的解題方式。接著介紹了貪心算法的一個典型應用，同時也指出了貪心算法在一些問題上的問題，比如無法得到最優(yōu)解等。本小節(jié)主要是理解貪心算法以及掌握解題思路，接下來的兩小節(jié)將進入實戰(zhàn)訓練，徹底理解和掌握貪心算法。