基本思想
從問題的某一個初始解出發(fā)，通過一系列的貪心選擇－當(dāng)前狀態(tài)下的局部最優(yōu)選擇，逐步逼近給定的目標(biāo)；
在每個階段，都作出一個按照（）某個評價函數(shù)最優(yōu)的決策，這個評價函數(shù)最優(yōu)稱為貪心準(zhǔn)則（類似于動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程）
2 基本步驟
和動態(tài)規(guī)劃類似
3 性質(zhì)
一般具有以下兩種限制
3.1 貪心選擇性質(zhì)
其指全局最優(yōu)解可以通過局部最優(yōu)解來得到（這也是和動態(tài)規(guī)劃的主要區(qū)別），動態(tài)規(guī)劃的算法通常以自底向上的方式來解各種子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每一次的貪心選擇就將所求問題簡化為規(guī)模更小的子問題。
3.2 最優(yōu)子結(jié)構(gòu)性質(zhì)
當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì)，問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可以用動態(tài)規(guī)劃或者貪心算法求解的關(guān)鍵特征。
4 和動態(tài)規(guī)劃的區(qū)別
5 問題
5.1 小數(shù)背包問題
還記得之前動態(tài)規(guī)劃講的背包問題嗎？那是01背包問題，無法用貪心算法來解決，因為貪心算法無法保證其背包的價值是全局最優(yōu)解（背包可能沒有裝滿），其適合于求解在將背包裝滿的情況下取得的最大價值。
題目：
問題描述：給定n種物品和一個背包。物品i
