一、基本思想
貪心算法采用每一步都選取當(dāng)前狀態(tài)下最優(yōu)的選擇，這樣雖然能得到局部最優(yōu)解，但是可能無法求得全局最優(yōu)解。
比如最簡單的背包問題，將背包的價(jià)值v與背包的重量w相除，得到v/w為單位重量下的物品價(jià)值，很明顯，這個(gè)值越高，這個(gè)物品越應(yīng)該被裝入，也就是貪心法“貪”的衡量標(biāo)準(zhǔn)。
我們每次都把v/w最高的物品放入，這樣我們每一步放入都不會(huì)虧，這就是貪心算法。
為什么貪心法只能用于背包問題而不能用于0/1背包問題? 見后面的分析。
二、貪心法基本性質(zhì)
1、最優(yōu)子結(jié)構(gòu)性質(zhì)
所謂最優(yōu)子結(jié)構(gòu)性質(zhì)，與動(dòng)態(tài)規(guī)劃算法一樣，貪心法也需要先求解子問題的解，進(jìn)而求解大問題的解，所以必須具有該性質(zhì)。這也是問題需要用到動(dòng)態(tài)規(guī)劃算法或貪心法時(shí)必須滿足的條件。
2、貪心選擇性質(zhì)
這是貪心法獨(dú)有的性質(zhì)，也是與動(dòng)態(tài)規(guī)劃法的區(qū)別之一。即每一步都選取當(dāng)前狀態(tài)下最優(yōu)的選擇。
對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終能夠?qū)е聠栴}的整體最優(yōu)解。
三、貪心法與動(dòng)態(tài)規(guī)劃法的區(qū)別
貪心算法性質(zhì)：每一步選擇都采取當(dāng)前狀態(tài)下最優(yōu)的選擇，而不著眼于全局最優(yōu)。
動(dòng)態(tài)規(guī)劃法（最優(yōu)子結(jié)構(gòu)+重疊子問題）——>自底向上
每一步的最優(yōu)解由上一步的局部最優(yōu)解進(jìn)行選擇得出，因此需要保存之前求解的所有子問題的最優(yōu)解備查。
貪心算法（最優(yōu)子結(jié)構(gòu)+貪心選擇性質(zhì)）——>自頂向下
每一步的最優(yōu)解由上一步的最優(yōu)解推導(dǎo)而得，當(dāng)前最優(yōu)解包含上一步的最優(yōu)解，但之前的最優(yōu)解不做保留。因此，在貪心算法中，做出的每一步?jīng)Q策都無法改變。
相同點(diǎn)：兩者都具有最優(yōu)子結(jié)構(gòu)性質(zhì)（每一步的選擇都將當(dāng)前問題簡化為一個(gè)規(guī)模更小的與原問題相同形式的子問題）
不同點(diǎn)：動(dòng)態(tài)規(guī)劃算法每步往往依賴于相關(guān)子問題的解，因而只有在解出相關(guān)子問題的解后才能做出選擇。而貪心算法只著眼于當(dāng)前狀態(tài)的最優(yōu)解，即局部最優(yōu)選擇，然后再去解出這個(gè)選擇后的狀態(tài)的相應(yīng)的子問題。（自底向上與自頂向下）
區(qū)別兩者的經(jīng)典例子：0/1背包問題與背包問題
四、典型例子
0/1背包與背包問題定義：
0/1背包問題需采用動(dòng)態(tài)規(guī)劃算法達(dá)到最優(yōu)解。
背包問題采用貪心算法可求解。
對(duì)于0/1背包問題，不能用貪心算法求解，為什么？
因?yàn)閷?duì)該問題用貪心選擇策略求解無法保證最后背包被裝滿，閑置的背包空間會(huì)影響每公斤背包的價(jià)值，進(jìn)而影響整體求解的最大價(jià)值。
0/1背包問題應(yīng)比較：選擇與不選擇兩種方案的哪種更優(yōu)，然后再進(jìn)行下一步選擇，這樣會(huì)形成多個(gè)重疊子問題，須用動(dòng)態(tài)規(guī)劃中的動(dòng)態(tài)規(guī)劃表進(jìn)行存儲(chǔ)。
