循序漸進(jìn)，搞懂什么是貪心算法

貪心算法簡(jiǎn)介

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

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

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

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

貪心算法的一般求解步驟

貪心算法沒(méi)有固定的解題套路，不過(guò)對(duì)一般情況，使用貪心算法，需要先對(duì)問(wèn)題進(jìn)行分析，可以參考如下的一般求解步驟。

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

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

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

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

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

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

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

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

def part_backpack(weight_bp, weights, values):
    """部分背包問(wèn)題"""
    # 計(jì)算單價(jià)并按從高到低排序
    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)先選單價(jià)更高的物品
    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))
    # 計(jì)算獲得的最大價(jià)值
    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('最大價(jià)值：', max_value)

Output:

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

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

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

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

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

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

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

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

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

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

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

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

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