基本思想

從問(wèn)題的某一個(gè)初始解出發(fā)，通過(guò)一系列的貪心選擇－當(dāng)前狀態(tài)下的局部最優(yōu)選擇，逐步逼近給定的目標(biāo)；

在每個(gè)階段，都作出一個(gè)按照（）某個(gè)評(píng)價(jià)函數(shù)最優(yōu)的決策，這個(gè)評(píng)價(jià)函數(shù)最優(yōu)稱(chēng)為貪心準(zhǔn)則（類(lèi)似于動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程）

2 基本步驟

和動(dòng)態(tài)規(guī)劃類(lèi)似

3 性質(zhì)

一般具有以下兩種限制

3.1 貪心選擇性質(zhì)

其指全局最優(yōu)解可以通過(guò)局部最優(yōu)解來(lái)得到（這也是和動(dòng)態(tài)規(guī)劃的主要區(qū)別），動(dòng)態(tài)規(guī)劃的算法通常以自底向上的方式來(lái)解各種子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每一次的貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。

3.2 最優(yōu)子結(jié)構(gòu)性質(zhì)

當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱(chēng)此問(wèn)題具有 最優(yōu)子結(jié)構(gòu)性質(zhì)，問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可以用動(dòng)態(tài)規(guī)劃或者貪心算法求解的關(guān)鍵特征。

4 和動(dòng)態(tài)規(guī)劃的區(qū)別

平面設(shè)計(jì)培訓(xùn),網(wǎng)頁(yè)設(shè)計(jì)培訓(xùn),美工培訓(xùn),游戲開(kāi)發(fā),動(dòng)畫(huà)培訓(xùn)

5 問(wèn)題

5.1 小數(shù)背包問(wèn)題

還記得之前動(dòng)態(tài)規(guī)劃講的背包問(wèn)題嗎？那是01背包問(wèn)題，無(wú)法用貪心算法來(lái)解決，因?yàn)樨澬乃惴o(wú)法保證其背包的價(jià)值是全局最優(yōu)解（背包可能沒(méi)有裝滿(mǎn)），其適合于求解在將背包裝滿(mǎn)的情況下取得的最大價(jià)值。

題目：

問(wèn)題描述：給定n種物品和一個(gè)背包。物品i