柚子快報邀請碼778899分享：【貪心算法】貪心算法

http://yzkb.51969.com/

貪心算法簡介

1.什么是貪心算法2.貪心算法的特點3.學(xué)習貪心的方向

點贊??收藏??關(guān)注?? 你的支持是對我最大的鼓勵，我們一起努力吧!??

1.什么是貪心算法

與其說是貪心算法，不如說是貪心策略。

貪心策略：解決問題的策略( 局部最優(yōu) —> 全局最優(yōu))。

把解決問題的過程分為若干步；解決每一步的時候，都選擇當前看起來 “最優(yōu)的” 解法；“希望” 得到全局最優(yōu)解。

接下來我們舉三個例子重點突然我們的貪心策略。

例一：找零問題

假設(shè)顧客拿著50塊錢去買一瓶4塊錢的飲料，你需要找顧客46塊錢。此時你只有面額20元、10元、5元、1元 若干個紙幣。我們要的是用最少的張數(shù)完成找零。

我給你找46塊錢肯定是一張一張給你湊成46塊錢。解決問題的時候整個問題就分為若干步，若干步就是一張一張的給你找。然后解決每一步的時候都選擇當前看起來 “最優(yōu)的” 解法。

當開始湊46塊錢的時候，剛開始肯定不會拿最小的1塊錢，我想的是最少的張數(shù)，那應(yīng)該是最快的湊夠46塊錢。所以第一次肯定選擇20塊。接下來在湊26塊錢，然后湊26塊錢，我依舊選擇當前看起來最優(yōu)的還是20塊錢。接下來湊6塊錢，20和10就不要考慮了，然后選5塊錢，接下來在選1塊錢，最后正好可以湊夠46塊錢。

回顧找零過程非常符合貪心策略，每次找錢都選擇當前能選擇的最大面額，選擇u最大面額就能用最少的張數(shù)湊成46塊錢。

例二：最小路徑和

我們在動態(tài)規(guī)劃遇到這道題。我想從左上角到達右下角，然后每次走只能向下走或者向右走。每個格子都是路徑，問從左上角達到右下角最小路徑和是多少？

這里已經(jīng)把問題拆分若干個了，從起點一步一步走就是。每一步走的時候都選擇當前看起來 “最優(yōu)的” 解法。從左上角開始走最終走到右下角貪心路徑和是10 。

但是可能會有個異或，這個10好像不對，我們直接觀察最小的路徑和是7?，F(xiàn)在先不管正確解法是什么，我們先搞懂什么是貪心策略。

例三：背包問題

物品編號從1~3，每個物品都有體積和價值。此時你手里還有一個最大容量為8的背包。每個物品都有無窮多個。然后問從這些物品種挑選一些物品放背包里，你所挑選東西的最大價值是多少？

這道題限制條件有點多，所以此時我們可能會有非常多的貪心策略。

比如只考慮體積這個限制條件，往背包裝的話，肯定會選擇體積最小的往背包里裝，因為裝的多價值可能更大。那只考慮體積的貪心策略的最大價值是8

還有只考慮價值，不是讓價值最大嗎，那就瘋狂裝價值最大的，但是因為背包容量的限制，只能裝一個價值為10的1號物品。然后去裝價值為7的2號物品，但是背包裝不下，所以接下來考慮價值為1的3號物品。在這種貪心策略下的最大價值是13

甚至還可以考慮單位體積價值，因為2最大但是因為容量的限制只能裝一個1號物品，然后考慮1.75但是裝不下，然后就考慮3號物品，你會發(fā)現(xiàn)這個策略和只考慮價值的策略是一樣的。

雖然上面想了三種貪心策略，但是細心發(fā)現(xiàn)這三種策略都錯，因為如果最大容量是8的話，那裝兩個2號物品的最大價值是14，比上面的都大。

雖然最后兩個例子貪心并沒有解決問題，但是希望已經(jīng)搞懂什么是貪心策略，就是 貪婪 + 鼠目寸光！說白了只考慮眼前的最優(yōu)解并不考慮全局的最優(yōu)解，然后通過眼前的最優(yōu)解，“希望” 得到全局最優(yōu)解。但是你會發(fā)現(xiàn)鼠目寸光并不一定能得到最后的結(jié)果。但是例子又是正確的，為什么正確？待會我們證明一下。

2.貪心算法的特點

1.貪心策略的提出

貪心策略的提出是沒有標準以及模板的可能每一道題的貪心策略都是不同的

2.貪心策略的正確性

因為有可能 “貪心策略” 是一個錯誤的方法，正確的貪心策略，我們是需要 “證明的”。

想證明一個貪心策略是錯的還是挺簡單的，舉一個反例就行了。就比如例二 更短的路徑和是7，例三 選擇兩個2號物品價值是最大的。這樣就把之前的貪心策略全部都給推翻了。所以想說一個貪心策略是錯的還是挺簡單的。但是例一 找零問題每次都去選可選的面額最大的就能用最少的張數(shù)湊成46塊錢，如何證明它是對的呢？

不能說憑感覺，此時看這樣一個例子，比如還是湊46，但是現(xiàn)在你的面額是 [20、18、10、5、1]，如果依舊按照貪心策略，你會選擇兩張20元的、一張5元的、一張1元的。但是由于此時有18塊錢，我可以選兩張18元的，再選一個10元的，才三張就能湊46元。然后你剛剛的貪心就不對了。所以不能說憑感覺，一定要有嚴格的證明。

常用的證明方法：數(shù)學(xué)中見過的所有證明方法。

證明：找零問題 [20、10、5、1]

我們先不管策略以及最優(yōu)解是什么，我們先證明一個性質(zhì)

假設(shè)最優(yōu)解用了20塊錢A張、10塊錢B張、5塊錢C張、1塊錢D張，此時我們先證明一個性質(zhì)B、C、D是有取值范圍的。

先考慮B，B的取值范圍有三種：B > 2， B = 2，B < 2 為什么考慮2，因為2張10可以湊成一張20。所以就把B分為>2，=2，<2，三種情況考慮。

我們很好證明前兩種情況不是B的最優(yōu)解，如果想用10，B用的數(shù)目超過2張，那么任意兩種10都可以用一張20替換，那用20來代替10絕對是比剛剛用兩種10塊更優(yōu)的。所以B絕對不可能超過2。

同理B=2也是不可能存在的，原因和上面一樣，如果B用了兩種10塊的，那直接用一張20的替換不是更優(yōu)的。

由此可以得到一個性質(zhì)，在最優(yōu)解中，B的張數(shù)絕對是小于2的或者可以說的小于等于1。在最優(yōu)解中B最多就是一張，要么沒有。

同理C是和B一樣的，要么C > 2、C = 2、C < 2，最終在最優(yōu)解中，C的數(shù)目最多1張，要么沒有。

同理D，因為5張D才可以湊出來一張C，D還是分三種情況：D > 5、D = 5、D < 5, 同理前面兩種是不存在的，D超過5張不如用一張C，D等于5張也是不如用一張C，所以D < 5 或者 D 小于等于 4

這是我們證明之前得到的性質(zhì)，10塊錢不超過1張，5塊錢不超過1張，1塊錢不超過4張。

接下來我們證明方法就是等效法。 設(shè)貪心策略最后用的張數(shù)是 [a、b、c、d]，最優(yōu)解 [A、B、C、D]。 接下來我們只要證明出來 a = A，b = B，c = C，d = D。那我們就可以說我們貪心就是最優(yōu)解。

先證明第一個a，回憶一下我們的貪心[a、b、c、d]怎么來的，我們的貪心策略是能用a就用a，直到a不能用了，在用b。所以用這個貪心策略可以得到 a >= A，絕對不可能是 a < A，如果小了就不是貪心策略，因為我們貪心策略就是能用20就盡量用20，所以a >= A。

然后我們還可以證明 a 不可能大于 A，如果 a > A，說明A比較小，別忘了整個錢數(shù)是不變的，如果A比較小，那么少的20塊錢就會讓B、C、D去湊，你會發(fā)現(xiàn)根本湊不出來，注意剛才的性質(zhì)10塊錢不超過1張，5塊錢不超過1張，1塊錢不超過4張，所能湊出來最大的錢是10 + 5 + 4 = 19，根本湊不出20。如果 a 不能大于 A。

因此得到一個結(jié)論： a = A

當 a = A，那 b c d 和 B C D 所湊的錢是一樣的。 當湊的錢是一樣的時候， 我們可以得到 b >= B，因為貪心我們會盡可能的選擇10塊錢，此時 b >= B ，同理我們也可以證明 b 不可能大于 B，原因和之前的一樣，如果B小的話，它會讓C和D湊10塊錢，但是C和D湊不出來10塊錢，C最多一張5塊錢，D最多四張1塊錢，5 + 4 = 9 最多湊9塊錢，根本湊不出10塊錢，所以 b 不可能大于 B。

因此 b = B

同理 c = C ，那 d 自然等于 D。

我們嚴格證明出來貪心策略和最優(yōu)解是一致的，因此貪心策略得到的結(jié)果絕對是最優(yōu)解。

3.學(xué)習貪心的方向

遇到不會的貪心題，很正常，把心態(tài)放平。

前期學(xué)習的時候，把重點放在貪心的策略上，把這個策略當成經(jīng)驗吸收。往后遇到相同類型的題目時可以用經(jīng)驗去解決這道問題。 當知道貪心是正確的時候，要想到如何去證明。

柚子快報邀請碼778899分享：【貪心算法】貪心算法

http://yzkb.51969.com/

推薦閱讀