基本思想

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

在每個階段，都作出一個按照（）某個評價函數(shù)最優(yōu)的決策，這個評價函數(shù)最優(yōu)稱為貪心準則（類似于動態(tài)規(guī)劃的狀態(tài)轉移方程）

2 基本步驟

和動態(tài)規(guī)劃類似

3 性質

一般具有以下兩種限制

3.1 貪心選擇性質

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

3.2 最優(yōu)子結構性質

當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有 最優(yōu)子結構性質，問題的最優(yōu)子結構性質是該問題可以用動態(tài)規(guī)劃或者貪心算法求解的關鍵特征。

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

平面設計培訓,網頁設計培訓,美工培訓,游戲開發(fā),動畫培訓

5 問題

5.1 小數(shù)背包問題

還記得之前動態(tài)規(guī)劃講的背包問題嗎？那是01背包問題，無法用貪心算法來解決，因為貪心算法無法保證其背包的價值是全局最優(yōu)解（背包可能沒有裝滿），其適合于求解在將背包裝滿的情況下取得的最大價值。

題目：

問題描述：給定n種物品和一個背包。物品i