貪心算法原理

貪心算法就是做出1系列選擇來使原問題到達(dá)最優(yōu)解。在每個決策點，都是做出當(dāng)前看來的最優(yōu)選擇，比如在活動選擇問題里面，我們總是在1個問題的基礎(chǔ)上選擇結(jié)束時間最早的活動，以后再在剩下活動的基礎(chǔ)上選出結(jié)束時間最早的活動，以此類推，直到?jīng)]有活動可以進行選擇。但是遺憾的是這類算法其實不是總能得到最優(yōu)解，并且是不是能得到最優(yōu)解還取決于對貪心策略的選擇。

1般來講，設(shè)計貪心算法觸及到下面幾個步驟：

1.肯定問題的最優(yōu)子結(jié)構(gòu)
2.基于問題的最優(yōu)子結(jié)構(gòu)設(shè)計1個遞歸算法
3.證明我們做出的貪心選擇，只剩下1個子問題
4.證明貪心選擇總是安全的
5.設(shè)計1個遞歸算法實現(xiàn)貪心策略
6.將貪心算法轉(zhuǎn)化為迭代算法

比如在活動選擇問題里面，我們就是肯定了互動最優(yōu)子結(jié)構(gòu)的性質(zhì)，我們在子問題Sj$S_j$里面選出1個基于上次選擇aj$a_j$的最早結(jié)束活動am$a_m$，使得Sj$S_j$的最優(yōu)解是由am$a_m$和Sm$S_m$的最優(yōu)解組成的。

更1般的來講，我們可以講貪心算法的設(shè)計步驟簡述為下面幾部：

1.將最優(yōu)化問題簡化為這樣的情勢：最初1個選擇以后，只剩下1個子問題需要求解！
2.證明在做出貪心選擇以后，原問題總是存在最優(yōu)解，即貪心選擇總是安全的！
3.證明在做出貪心選擇以后，剩下的子問題滿足性質(zhì)：其最優(yōu)解與做出選擇的組合在1起得到原問題的最優(yōu)解，即最優(yōu)子結(jié)構(gòu)

貪心算法的兩大性質(zhì)

貪心算法有兩個重要的性質(zhì)：

• 貪心選擇性質(zhì)
• 最優(yōu)子結(jié)構(gòu)性質(zhì)

下面我們來詳細(xì)討論這兩個性質(zhì)

貪心選擇性質(zhì)

第1個關(guān)鍵要素就是貪心選擇性質(zhì):我們可以做出局部最優(yōu)選擇來構(gòu)造最優(yōu)解。也就是說，我們在做出選擇時，總是以當(dāng)前的情況為基礎(chǔ)做出最優(yōu)選擇的，而不用斟酌子問題的解！

這要是和動態(tài)計劃最大的不同的地方，我們知道

• 在動態(tài)計劃中，在每次做出1個選擇的時候總是要將所有選擇進行比較以后才能肯定到底采取哪種選擇，而這類選擇的參考根據(jù)是以子問題的解為基礎(chǔ)的，所以動態(tài)計劃總是采取自下而下的方法來，先得到子問題的解，再通過子問題的解構(gòu)造原問題的解。就算是自上而下的算法也是先求出子問題的解，通過遞歸調(diào)用自下而上的返回每個子問題的最優(yōu)解
• 在貪心算法中，我們總是在原問題的基礎(chǔ)上做出1個選擇，然后求解剩下的唯1子問題，貪心算法歷來都不依賴子問題的解，不過有可能會依賴上1次做出的選擇，所以貪心算法是自上而下的。1步1步的選擇將原問題1步步消減得更小

固然，我們必須證明每個步驟做出的貪心選擇都可以生玉成局最優(yōu)解！我們再活動選擇問題里面是這樣的做的，首先假定有1個最優(yōu)解，然后將做出的選擇替換進去得到另外1個最優(yōu)解！

最優(yōu)子結(jié)構(gòu)

如果1個問題的最優(yōu)解包括其子問題的最優(yōu)解，那末就稱這個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)！我們知道最優(yōu)子結(jié)構(gòu)這個性質(zhì)是動態(tài)計劃和貪心算法都必須具有的關(guān)鍵性質(zhì)。

貪心算法vs動態(tài)計劃

貪心算法和動態(tài)計劃都有1些共同的性質(zhì)，比如最優(yōu)子結(jié)構(gòu)，有些問題我們可以采取動態(tài)計劃來解決，也能夠采取貪心算法來結(jié)局，這二者之間有細(xì)微的差別！下面我們通過研究1個問題來辨別之間的差別！
下面有兩個經(jīng)典的算法問題:

• 0⑴背包問題：我們有1堆物品S={a1,a2,...,an}$S=lbrace a_1,a_2,...,a_n brace$,每個物品ai$a_i$都有1個重量wi$w_i$和1個價值vi$v_i$.現(xiàn)在有1個背包，這個背包的容量為W$W$,現(xiàn)在要將這些物品在不超越背包容量的情況下選擇性的放入背包，使得背包里面物品的價值最大，物品不能只選取其中1部份，必須選擇全部，或不選！

• 分?jǐn)?shù)背包問題：這個問題和上面的問題比較類似，唯1不同的就是該問題里面的物品可以進行分割，便可以只選取1個物品ai$a_i$的1部份

雖然上面兩個問題比較類似，但是貪心算法可以求解第2個問題而不能求解0⑴背包問題，為了求解分?jǐn)?shù)背包問題，我們首先得到每個物品單位重量的價值vi/wi$v_i/w_i$,那末我們要設(shè)計1個貪心策略來使得裝入背包物品的價值最大。我們的第1直覺肯定是要選擇單位重量價格最高的嘍，讓后再選擇物品里面第2高的，1次類推直到裝滿背包為止！

下面我們來證明1下上面貪心選擇的料想：

證明:

我們首先假定我們有1個最優(yōu)解A1$A_1$,那末我們首先找到A1$A_1$里面平均價值最高的物品am$a_m$，讓后我們將用商品里面平均價值最高的物品a1$a_1$將am$a_m$進行全部替換或部份替換得到解A2$A_2$，又因v1/w1≥vm/wm$v_1/w_1 geq v_m/w_m$所以A2$A_2$的總價值高于A1$A_1$的總價值，這A1$A_1$是最優(yōu)解矛盾，因而得到A1$A_1$里面包括平均價值最高的物品。

因而我們得到最優(yōu)子結(jié)構(gòu)Si=Sk+ak$S_i = S_k +a_k$，ak$a_k$是Si$S_i$里面平均價值最高的，Sk$S_k$是選擇ak$a_k$剩下來的物品。
為了說明這個貪心策略對0⑴背包問題無效，我們采取下面的例子

我們有3個物品和1個容量為50的背包，這3個物品<重量,價值>分別為:a1<10,60>,a2<20,100>,a3<30,120>$a1<10,60>,a2<20,100>,a3<30,120>$.

如果依照上面的貪心策略來選擇的話，首先是選擇a1$a1$,然后再選擇a2$a2$再選擇a3$a3$.但是這樣做真的可以到達(dá)最大價值么？未見得：

所以上面的貪心選擇將不能解決0⑴背包問題，但是卻可以完善的解決分?jǐn)?shù)背包問題，那末0⑴背包問題要怎樣解決，由于這兩個背包問題都有1個很重要的性質(zhì)，那就是最優(yōu)子結(jié)構(gòu)，因而乎動態(tài)計劃這個利器就要出手啦！
我們將在另外1篇文章里面介紹0⑴背包問題和分?jǐn)?shù)背包問題！

文章中難免有疏漏，望批評指正！