一、概述

1.設計思想

貪心演算法通過一系列選擇來得到問題的解，所做的每個選擇都是當前狀態下區域最好選擇，即貪心選擇，

貪心演算法并不從整體最優上加以考慮，所做的選擇只是在某種意義上的區域選擇，在一些情況下，即使貪心演算法不能得到整體最優解，但其最終結果確實最優解的很好的近似解，

2.基本要素

（1）貪心選擇性質

貪心演算法所做的選擇可以依賴以往所做過的選擇，但絕不依賴將來所做的選擇，也不依賴子問題的解，

（2）最優子結構性質

當一個問題的最優解中包含了子問題的最優解時，則稱該問題具有最優子結構特性，

3.存在的問題

（1）不能保證求得的最后解是最佳的；
（2）不能用來求最大或最小解問題；
（3）只能求滿足某些約束條件的可行解的范圍，

4.演算法比較

名稱

同

異

貪心演算法

都要求問題具有最優子結構性質

不依賴將來和子問題的解

自頂向下進行求解

具有貪心選擇性質

動態規劃演算法

往往依賴相關子問題的解

自底向上進行求解

具有重疊子問題性質

二、例題總結

1.活動安排問題

【問題描述】設有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源（如演講會場等），而在同一時間內只有一個活動能使用這一資源，每個活動i都有一個要求使用該資源的起始時間si和結束時間fi，如果選擇了活動i，則它在半開區間[si,fi)與區間[sj,fj)內占用資源，若區間[si,fi)與區間[sj,fj)不相交，則稱活動i和j是相容的，也就是說，當si≥fj或sj≥fi時，活動i與活動j相容，

【演算法設計】由于活動占用資源的時間沒有限制，因此，選擇最早結束時間作為貪心策略更加合理，目的是使剩余時間段最大化，以便安排盡可能多相容的活動，

【演算法實作】

陣列f中元素按結束時間非降序排列，若未按此序排列，可以用O(nlogn)做時間重排，

2.背包問題

【問題描述】設背包容量為C，n個物品，物品價值和重量為v[i],w[i]，物品可以只裝一部分，

【演算法設計】不存在0-1要求，先裝單價最貴的，再裝單價次貴的，依此貪心策略一直進行下去，直到背包裝滿，

【演算法實作】 O(nlogn)

3.最優裝載問題

【問題描述】設有一輪船能裝載的貨物重量為C，有n個集裝箱，重量為w[i]，問怎樣可以裝盡可能多的集裝箱，

【演算法設計】先裝最輕的，再裝次輕的，依此貪心策略一直進行下去，直到輪船裝滿，

【演算法實作】 O(nlogn)

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/296233.html

標籤：其他

上一篇：劍指offer

下一篇：嚴格次小生成樹