1. 貪婪法定義

貪婪法，又稱貪心算法，是尋找最優解問題的常用方法，這種方法模式一般將求解過程分成若干個步驟，但每個步驟都應用貪心原則，選取當前狀態下最好的或最優的選擇（局部最有利的選擇），并以此希望最后堆疊出的結果也是最好或最優的解。

貪婪法的每次決策都以當前情況為基礎并根據某個最優原則進行選擇，不從整體上考慮其他各種可能的情況。

2. 貪婪法劣勢

貪婪法與其他方法最大的不同在于，貪婪法每一步選擇完局部最優解之后就確定了，不再進行回溯處理，也就是說，每一個步驟的局部最優解確定以后，就不再修改，直到算法結束。

因為不進行回溯處理，貪婪法只在很少的情況下可以得到真正的最優解，比如最短路徑問題、圖的最小生成樹問題。在大多數情況下，由于選擇策略的“短視”，貪婪法會錯過真正的最優解，而得不到問題的真正答案。

但是貪婪法簡單、高效，省去了為找最優解可能需要的窮舉操作，可以得到與最優解比較接近的近似最優解，通常作為其他算法的輔助算法來使用。

3. 設計步驟

貪婪法的基本設計思想有以下三個步驟：

• 建立對問題精確描述的數學模型，包括定義最優解的模型；
• 將問題分解為一系列的子問題，同時定義子問題的最優解結構；
• 應用貪心原則確定每個子問題的局部最優解，并根據最優解的模型，用子問題的局部最優解堆疊出全局最優解。

舉個例子：某國發行的貨幣有 25 分、10 分、5 分和 1 分四種硬幣，如果你是售貨員且要找給客戶 41 分錢的硬幣，如何安排才能找給客人的錢既正確且硬幣的個數又最少？

這個問題的子問題定義就是從四種幣值的硬幣中選擇一枚，使這個硬幣的幣值和其他已經選擇的硬幣的幣值總和不超過 41 分錢。

子問題的最優解結構就是在之前的步驟已經選擇的硬幣再加上當前選擇的一枚硬幣，當然，選擇的策略是貪婪策略，即在幣值總和不超過 41 的前提下選擇幣值最大的那種硬幣。按照這個策略，第一步會選擇 25 分的硬幣一枚，第二步會選擇 10 分的硬幣一枚，第三步會選擇 5 分的硬幣一枚，第四步會選擇 1 分的硬幣一枚，總共需要 4 枚硬幣。

上面的例子得到的確實是一個最優解，但是很多情況下貪婪法都不能得到最優解。同樣以找零錢為例，假如，某國貨幣發行為 25 分、20 分、5 分和 1 分四種硬幣，這時候找 41 分錢的最優策略是 2 枚 20 分的硬幣加上 1 枚 1 分硬幣，一共 3 枚硬幣，但是用貪婪法得到的結果卻是 1 枚 25 分硬幣、3 枚 5 分硬幣和 1 枚 1 分硬幣，一共 5 枚硬幣。

4. 實例

貪婪法的經典例子—— 0-1 背包問題：有 N 件物品和一個承重為 C 的背包（也可定義為體積），每件物品的重量是 wi，價值是 pi，求解將哪幾件物品裝入背包可使這些物品在重量總和不超過 C 的情況下價值總和最大。

背包問題（Knapsack Problem）是此類組合優化的 NP 完全問題的統稱，如貨箱裝載問題、貨船載物問題等，因問題最初來源于如何選擇最合適的物品裝在背包中而得名，這個問題隱含了一個條件，每個物品只有一件，也就是限定每件物品只能選擇 0 個或 1 個，因此又被稱為 0-1 背包問題。

來看一個具體的例子，有一個背包，最多能承載重量為 C=150 的物品，現在有 7 個物品（物品不能分割成任意大小），編號為 1~7，重量分別是 wi=[35,30,60,50,40,10,25]，價值分別是 pi=[10,40,30,50,35,40,30]，現在從這 7 個物品中選擇一個或多個裝入背包，要求在物品總重量不超過 C 的前提下，所裝入的物品總價值最高。

常見的貪婪策略：

1. 根據物品價值選擇，每次都選價值最高的物品；
2. 根據物品重量選擇，每次都選擇重量最輕的物品；
3. 定義一個價值密度的概念，每次選擇都選價值密度最高的物品，物品的價值密度 si 定義為 pi/wi;

總結

以上是生活随笔為你收集整理的算法设计思想（2）— 贪婪法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。