貪心算法介紹

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

1. 貪心算法介紹

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

2. 貪心算法思路介紹

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

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

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

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

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

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

4. 貪心算法的典型應(yīng)用

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

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

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

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

很明顯，我們貪心的策略應(yīng)該選擇第三種，這樣能兼顧寶物價值和重量，找到滿足要求的最優(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)

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

pre_value = []
for i in range(len(ts)):
    pre_value.append([ts[i], ws[i], ts[i] / ws[i]])
# 按照單位價值從大到小進(jìn)行排序
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:
        # 可以取走寶物的一部分，達(dá)到最大裝載
        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]])
    # 將寶物按單位價值從大到小進(jìn)行排序
    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:
            # 可以取走寶物的一部分，達(dá)到最大裝載
            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)裝載問題、教室調(diào)度問題等等，都可以使用貪心算法解決。但是我們一定要找對貪心的值，這樣才能確保得到最優(yōu)的解。

6. 小結(jié)

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