循序漸進，搞懂什么是貪心算法

貪心算法簡介

貪心算法（greedy algorithm）又稱貪婪算法，指在求解最優(yōu)化問題時，每一步都選擇在當(dāng)前狀態(tài)下最好或最優(yōu)的策略，從而逐步推導(dǎo)出最優(yōu)解的算法。

貪心算法不從整體最優(yōu)上加以考慮，它所做出的選擇只是局部最優(yōu)選擇。這種策略的顯著特點是“目光短淺”，只看重眼前最好的選擇，而不考慮更長遠的結(jié)果。因此，貪心算法不是對所有問題都能得到整體最優(yōu)的解。對于一些問題，它只能得到局部最優(yōu)解，局部最優(yōu)解并不一定是整體最優(yōu)解，不過，通常是近似最優(yōu)解。

貪心算法的典型應(yīng)用包含：部分背包問題、霍夫曼編碼（huffman coding）、最小生成樹（普利姆算法，prim's algorithm）、單源最短路徑問題（迪杰斯特拉算法，Dijkstra's algorithm）等。

貪心算法的關(guān)鍵是構(gòu)造適合的貪心策略。貪心算法執(zhí)行時根據(jù)貪心策略做出最優(yōu)選擇，不考慮各種可能的情況，省去了窮盡所有可能的選項而耗費的時間。因此貪心算法的運行效率高，運行時間較短。

貪心算法的一般求解步驟

貪心算法沒有固定的解題套路，不過對一般情況，使用貪心算法，需要先對問題進行分析，可以參考如下的一般求解步驟。

1. 問題定義：明確問題的輸入、輸出和目標(biāo)。

2. 狀態(tài)定義：將問題分解為多個階段，每個階段都有一個狀態(tài)。狀態(tài)通常由問題的某些屬性表示。

3. 確定貪心策略：在每個階段，根據(jù)當(dāng)前狀態(tài)選擇最優(yōu)決策，以期望達到全局最優(yōu)解。這個最優(yōu)決策通常是最優(yōu)子結(jié)構(gòu)的一部分，問題的最優(yōu)解可以通過其子問題的最優(yōu)解來獲得，則問題具有最優(yōu)子結(jié)構(gòu)，這意味著每個階段的最優(yōu)決策都是全局最優(yōu)解的一部分。

4. 代碼實現(xiàn)：根據(jù)上述步驟設(shè)計貪心算法，編寫代碼。通常，貪心算法包括一個循環(huán)，每次循環(huán)中都選擇當(dāng)前最優(yōu)決策，并更新狀態(tài)。

5. 算法分析：分析貪心算法的正確性和可行性。

貪心算法實現(xiàn)舉例

貪心算法最簡單易懂的應(yīng)用是部分背包問題，下面直接看一個例子。

假設(shè)有一個能裝下50磅重的背包，有5件不同的物品，它們的重量分別為[5, 10, 30, 20, 5]，價值分別為[80, 200, 300, 150, 30]，這5件物品都可以按每磅獲取其中的一部分。為了使背包裝下的物品價值最高，應(yīng)該在背包中裝哪些物品？最高價值是多少？

def part_backpack(weight_bp, weights, values):
    """部分背包問題"""
    # 計算單價并按從高到低排序
    unit_value = []
    for i in range(len(weights)):
        unit_value.append((f'w{i+1}', weights[i], values[i]/weights[i]))
    unit_value = sorted(unit_value, key=lambda x: x[2], reverse=True)
    # 開始貪心選擇，優(yōu)先選單價更高的物品
    result = []
    i = 0
    # 能全部裝下的物品
    while i < len(unit_value):
        if unit_value[i][1] > weight_bp:
            break
        weight_bp -= unit_value[i][1]
        result.append(unit_value[i])
        i += 1
    # 能部分裝下的物品
    if i < len(unit_value):
        part_item = list(unit_value[i])
        part_item[1] = weight_bp
        result.append(tuple(part_item))
    # 計算獲得的最大價值
    max_value = sum(r[1]*r[2] for r in result)
    return result, max_value


weight_bp = 50
weights = [5, 10, 30, 20, 5]
values = [80, 200, 300, 150, 30]
result, max_value = part_backpack(weight_bp, weights, values)
print(result)
print('最大價值：', max_value)

Output:

[('w2', 10, 20.0), ('w1', 5, 16.0), ('w3', 30, 10.0), ('w4', 5, 7.5)]
最大價值：617.5

問題要求在5種不同重量和價值的物品中選擇一部分裝進背包，使最終裝下的物品總價值最高。所以問題的輸入就是背包容量、每件物品的重量和價值，輸出就是每件物品裝了多少，最終裝進背包的總價值是多少，目標(biāo)是使背包里裝下的物品總價值最高。

要使總價值最高，最直觀的方式就是優(yōu)先裝單位重量價值最高的物品，首先計算每件物品的單價（每磅的價值），貪心策略就是優(yōu)先選擇單價更高的物品。每往背包里裝一樣物品，都判斷當(dāng)前的背包是否已經(jīng)裝滿，判斷下一件物品是否可以裝進背包，以及下一件物品是全部裝進背包還是部分裝進背包。這就是狀態(tài)的定義和更新。

在上面的例子中，計算每件物品的單價后，將物品按單價從高到低排序，這樣可以依次往背包里裝單價排序靠前的物品。如果前面的物品重量小于背包容量，可以全部被裝進背包，當(dāng)背包剩余的容量越來越小，如果剩余容量小于背包外單價最高的物品重量，則該物品不能被全部裝下，但可以被部分裝下，此時將該物品的一部分裝進背包，把背包填滿（也可能裝完某件物品時背包容量剛好為0）。裝滿背包后，記錄裝下了哪些物品，計算物品的總價值，得到問題的答案。

背包問題分為0-1背包問題和部分背包問題，如果每件物品都是一個整體，要么被裝進背包，要么不被裝進背包，這種要么裝要么不裝的情況被稱為0-1背包問題。如果每件物品都可以被部分裝進背包，如上面的例子每件物品都可以按磅“散裝”，這種物品可以被拆分的情況被稱為部分背包問題。

《算法導(dǎo)論》進行了論證，貪心算法不適用于0-1背包問題，但適用于部分背包問題。因為在0-1背包問題中，按貪心策略取物品不一定能填滿背包，空余的空間會拉低物品的平均價值，從而導(dǎo)致貪心算法的結(jié)果只是次優(yōu)解。而部分背包問題中，背包總是能被裝滿，按貪心策略取物品，總是能得到最優(yōu)解。本文后面附上《算法導(dǎo)論》中的貪心算法的部分內(nèi)容。

《算法導(dǎo)論》中的貪心算法

貪心算法是通過做一系列的選擇來給出某一問題的最優(yōu)解。對算法中的每一個決策點，做一個當(dāng)時（看起來是）最佳的選擇。這種啟發(fā)式策略并不是總能產(chǎn)生出最優(yōu)解，但它常常能給出最優(yōu)解。
在實際設(shè)計貪心算法時，通常直接做出貪心選擇來構(gòu)造子結(jié)構(gòu)，以產(chǎn)生一個待優(yōu)化解決的子問題，或者，根據(jù)貪心選擇來構(gòu)造最優(yōu)子結(jié)構(gòu)。
更一般地，可以根據(jù)如下步驟來設(shè)計貪心算法：

1. 將優(yōu)化問題轉(zhuǎn)換成這樣的一個問題，即先做出選擇，再解決剩下的一個子問題。
2. 證明原問題總是有一個最優(yōu)解是做貪心選擇得到的，從而說明貪心選擇的安全。
3. 說明在做出貪心選擇后，剩余的子問題具有這樣一個性質(zhì)。即如果將子問題的最優(yōu)解和我們所做的貪心選擇聯(lián)合起來，可以得出原問題的一個最優(yōu)解。

貪心算法是否能夠解決一個特定的最優(yōu)化問題？一般來說不是，但是貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)是兩個關(guān)鍵的特點。如果我們能夠證明問題具有這些特點，那么就可以設(shè)計出它的一個貪心算法。

貪心選擇性質(zhì)
第一個關(guān)鍵特點是貪心選擇性質(zhì)，一個全局最優(yōu)解可以通過局部最優(yōu)（貪心）選擇來達到。換句話說，當(dāng)考慮做何選擇時，我們只考慮當(dāng)前問題最佳的選擇而不考慮子問題的結(jié)果。
這一點是貪心算法不同于動態(tài)規(guī)劃之處。在動態(tài)規(guī)劃中，每一步都要做出選擇，但是這些選擇依賴于子問題的解。因此，解動態(tài)規(guī)劃問題一般是自底向上，從小子問題處理至大子問題。在貪心算法中，我們所做的總是當(dāng)前看似最佳的選擇，然后再解決選擇之后所出現(xiàn)的子問題。貪心算法所做的當(dāng)前選擇可能要依賴于已經(jīng)做出的所有選擇，但不依賴于有待做出的選擇或子問題的解。因此，不像動態(tài)規(guī)劃方法那樣自底向上地解決子問題，貪心策略通常是自頂向下地做的，一個一個地做出貪心選擇，不斷地將給定的問題實例規(guī)約為更小的問題。
當(dāng)然，我們必須證明在每一步所做的貪心選擇最終能產(chǎn)生一個全局最優(yōu)解，這也正是需要技巧的所在。一般來說，在證明中先考察一個全局最優(yōu)解，然后證明可對該解加以修改，使其采用貪心選擇，這個選擇將原問題變?yōu)橐粋€相似的、但更小的問題。
貪心選擇性質(zhì)在面對子問題做出選擇時，通常能幫助我們提高效率，通常對數(shù)據(jù)進行處理或選用合適的數(shù)據(jù)結(jié)構(gòu)（優(yōu)先隊列），能夠使貪心選擇更加快速，因而產(chǎn)生出一個高效的算法。

最優(yōu)子結(jié)構(gòu)
對一個問題來說，如果它的一個最優(yōu)解包含了其子問題的最優(yōu)解，則稱該問題具有最優(yōu)子結(jié)構(gòu)。這個性質(zhì)是用來對動態(tài)規(guī)劃以及貪心算法的可應(yīng)用性進行評價的關(guān)鍵一點?；趯ψ顑?yōu)子結(jié)構(gòu)的觀察，我們能夠?qū)懗雒枋鲆粋€最優(yōu)解值的遞歸式。
在貪心算法中使用最優(yōu)子結(jié)構(gòu)時，通常是用更直接的方式。假設(shè)在原問題中做了一個貪心選擇而得到了一個子問題，真正要做的是證明將此子問題的最優(yōu)解與所做的貪心選擇合并后，的確可以得到原問題的一個最優(yōu)解。這個方案意味著要對子問題采用歸納法，來證明每個步驟中所做的貪心選擇最終會產(chǎn)生一個最優(yōu)解。

貪心法與動態(tài)規(guī)劃
因為貪心法和動態(tài)規(guī)劃都利用了最優(yōu)子結(jié)構(gòu)性質(zhì)，故人們往往會在貪心解足以解決問題的場合下，給出一個動態(tài)規(guī)劃解，或者在需要動態(tài)規(guī)劃方法的場合下使用貪心方法。為說明這兩種算法之間的細微區(qū)別，我們來考察一個經(jīng)典最優(yōu)化問題的兩種變形。
0-1背包問題是這樣的：有一個賊在偷竊一家商店時發(fā)現(xiàn)有n件物品，第i件物品值v_i元，重w_i磅。此處v_i和w_i都是整數(shù)。他希望帶走的東西越值錢越好，但他的背包中至多只能裝下W磅的東西，W為一整數(shù)。應(yīng)該帶走哪幾樣?xùn)|西？（這個問題之所以稱之為0-1背包問題，是因為每件物品或被帶走，或被留下，小偷不能只帶走某個物品的一部分或帶走兩次以上的同一物品。）
部分背包問題中，場景等與上面問題一樣，但是竊賊可以帶走物品的一部分，而不必作出0-1的二分選擇?？梢园?-1背包問題的一件物品想象成一個金錠，而部分背包問題中的一件物品則更像金粉。
兩種背包問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對0-1背包問題，考慮重量至多為W磅的最值錢的一包東西。如果我們從中去掉物品j，余下的必須是竊賊從除j以外的n-1件物品中，可以帶走的重量至多為W-w_j的最值錢的一包東西。對部分背包問題，考慮如果我們從最優(yōu)貨物中去掉某物品j的重量w，則余下的貨物必須是竊賊可以從n-1件原有物品和物品j的w_j-w磅重中可帶走的、重量至多為W-w的、最值錢的一包東西。
雖然這兩個問題非常相似，但部分背包問題可用貪心策略來解決，而0-1背包問題卻不行。為解決部分背包問題，先對每件物品計算其每磅的價值v_i/w_i，按照一種貪心策略，竊賊開始時對具有最大每磅價值的物品盡量多拿一些。如果他拿完了該物品而仍可以取一些其他物品時，他就再取具有次大的每磅價值的物品，一直持續(xù)下去，直到不能再取為止。這樣，通過按每磅價值來對所有物品排序，貪心算法就可以以O(shè)(nlogn)時間運行。
為搞清楚為什么這種貪心策略不適用于0-1背包問題，讓我們來看一個該問題的實例?？偣灿腥锲罚嘲扇菁{50磅重的東西，物品1重10磅，價值60元，物品2重20磅，價值100元，物品3重30磅，價值120元。這樣，物品1每磅6元，大于物品2的每磅5元和物品3的每磅4元，按照貪心策略的話就會最先取物品1，然而，經(jīng)過分析，最優(yōu)解取的是物品2和3，留下了物品1，兩種包含物品1的可能解都是次優(yōu)的。
對于部分背包問題，在按照貪心策略先取物品1以后，還可以取物品2，取物品3的一部分，確實可以產(chǎn)生一個最優(yōu)解。在0-1背包問題中不應(yīng)取物品1的原因在于這樣無法將背包填滿，空余的空間就降低了他的貨物的有效每磅價值。在0-1背包問題中，當(dāng)我們在考慮是否要把一件物品加到背包中時，必須對把該物品加進去的子問題的解與不取該物品的子問題的解進行比較。由這種方式形成的問題導(dǎo)致了許多重疊子問題（這是動態(tài)規(guī)劃的一個特點）。所以，我們可以用動態(tài)規(guī)劃來解決0-1背包問題。