柚子快報邀請碼778899分享：【算法】貪心算法

http://yzkb.51969.com/

貪心算法

1. 貪心介紹2. 貪心本質(zhì)3. 最優(yōu)裝載問題（1）問題分析（2）算法實現(xiàn)（3）算法分析

1. 貪心介紹

貪心算法總是做出當(dāng)前最好的選擇，期望通過局部最優(yōu)選擇得到全局最優(yōu)的解決方案。但貪心不是從整體最優(yōu)來考慮的，一旦做出選擇，不會再改變，只能達(dá)到某種意義上的局部最優(yōu)。

簡記為：想要當(dāng)下最好的，但會導(dǎo)致目光短淺

2. 貪心本質(zhì)

應(yīng)用情景：當(dāng)出現(xiàn)兩個特性——貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)時可用。

（1）貪心選擇性質(zhì)：指原問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇得到。運用同一規(guī)則，原問題可拆分為一個個相似的子問題，而后的每一步都是當(dāng)前最優(yōu)的選擇。但其依賴于當(dāng)前已做出的選擇，無回溯過程。

（2）最優(yōu)子結(jié)構(gòu)性質(zhì)：指一個問題的最優(yōu)解包含其子問題的最優(yōu)解。如：原問題：S={a1,a2,a3,ai...an}，轉(zhuǎn)化為子問題：{ai},S-{ai}。即通過貪心選擇當(dāng)前最優(yōu)解{ai}后，轉(zhuǎn)化為求解子問題S-{ai}。

求解步驟： （1）貪心策略：選擇當(dāng)前看上去最好的一個。如：最紅的蘋果是最好的，則每一次都選擇最紅的。 （2）局部最優(yōu)解：每一次取到的結(jié)果記為ak（k=1，2，3…） （3）全局最優(yōu)解：把所有局部最優(yōu)解整合為一個最優(yōu)解{a1,a2,…}

3. 最優(yōu)裝載問題

有一天，海盜們截獲了一艘裝滿各種各樣古董的貨船，每件古董都價值連城，一旦打碎就失去了價值。雖然海盜船足夠大，但載重為c，每件古董的重量為wi，海盜們絞盡腦汁要把盡可能多的寶貝裝上海盜船，該怎么辦呢？

假設(shè)c為30，8件古董，價值分別為4，10，7，11，3，5，14，2

（1）問題分析

盡可能多：排序，每次選最小的裝入

（2）算法實現(xiàn)

可以用一維數(shù)組w[]存儲古董的數(shù)量

（1）借助c++中的排序函數(shù)sort （頭文件#include）

排序算法如下：

sort(begin,end)//參數(shù)begin和end表示一個范圍，分別為待排序數(shù)組的首地址和尾地址，默認(rèn)為升序

（2）代碼如下：

double tmp=0.0;//tmp為已裝載到船上的古董的重量

int ans=0;//ans為已裝載的古董個數(shù)

for(int i=0;i

{

twp+=w[i];

if(tmp<=c)

ans++;

else

break;

}

cout<

（3）算法分析

（1）時間復(fù)雜度： ①sort函數(shù)，平均時間復(fù)雜度為O(nlogn)； ②輸入和貪心策略求解的兩個for循環(huán)均為O(n)； 故，總的為O(nlogn)。

（2）空間復(fù)雜度：在程序中使用了tmp、ans等輔助變量，為O(1)。

柚子快報邀請碼778899分享：【算法】貪心算法

http://yzkb.51969.com/

好文鏈接