文章內容來自王曉華老師

?

貪心算法，是尋找最優解問題的常用方法
這種方法模式一般將求解過程分成若干個步驟，但每個步驟都應用貪心原則，選取當前狀態下最好的或最優的選擇（局部最有利的選擇），并以此希望最后堆疊出的結果也是最好或最優的解。
因為不進行回溯處理，貪婪法只在很少的情況下可以得到真正的最優解，比如最短路徑問題、圖的最小生成樹問題。
在大多數情況下，由于選擇策略的“短視”，貪婪法會錯過真正的最優解，而得不到問題的真正答案。但是貪婪法簡單、高效，省去了為找最優解可能需要的窮舉操作，可以得到與最優解比較接近的近似最優解，通常作為其他算法的輔助算法來使用。

?

貪婪法的基本設計思想有以下三個步驟：
? 建立對問題精確描述的數學模型，包括定義最優解的模型；
? 將問題分解為一系列的子問題，同時定義子問題的最優解結構；
? 應用貪心原則確定每個子問題的局部最優解，并根據最優解的模型，用子問題的局部最優解堆疊出全局最優解。

?

背包問題：有 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 的前提下，所裝入的物品總價值最高。

思路

　　常見的貪婪策略有三種：第一種策略是根據物品價值選擇，每次都選價值最高的物品，此時包中物品總重量是 130，總價值是 165。第二種策略是根據物品重量選擇，每次都選擇重量最輕的物品，此時包中物品總重量是 140，總價值是 155。第三種策略是定義一個價值密度的概念，每次選擇都選價值密度最高的物品，物品的價值密度 si 定義為 pi/wi，此時包中物品的總重量是 150，總價值是 170，我們可以選用合適的策略，得到較優解

?

通用的解題思路

/**GreedyAlgo() 函數是貪婪算法的主體結構，包括子問題的分解和選擇策略的選擇都在這個函數中。
能夠明顯看出來這個算法使用了迭代法的算法模式，當然，這個算法主體的實現還可以使用遞歸法，
正如函數所展示的那樣，它可以作為此類問題的一個通用解決思路： */ void GreedyAlgo(KNAPSACK_PROBLEM *problem, SELECT_POLICY spFunc) {int idx;int ntc = 0;//spFunc 每次選最符合策略的那個物品，選后再檢查while((idx = spFunc(problem->objs, problem->totalC - ntc)) != -1){//所選物品是否滿足背包承重要求？if((ntc + problem->objs[idx].weight) <= problem->totalC){problem->objs[idx].status = 1;ntc += problem->objs[idx].weight;}else{//不能選這個物品了，做個標記后重新選problem->objs[idx].status = 2; }}PrintResult(problem->objs); } /**spFunc 參數是選擇策略函數的接口，通過替換這個參數，可以實現上文提到的三種貪婪策略，
分別得到各種貪婪策略下得到的解。以第一種策略為例，每次總是選擇 price 最大的物品，可以這樣實現： */int Choosefunc1(std::vector<OBJECT>& objs, int c) {int index = -1; //-1表示背包容量已滿int mp = 0;for(int i = 0; i < static_cast<int>(objs.size()); i++){if((objs[i].status == 0) && (objs[i].price > mp)){mp = objs[i].price;index = i;}}return index; }

?

lua代碼實現

-- 物品 -- obj = { -- weight = 0, -- price = 0, -- status = 0 -- 0未選中 1已選中 2已不可選 -- } -- 背包 -- bag = { -- obj_list = {}, -- totalC = 0 -- }local function choose_func1(obj_bag, use_c)local index = -1 ---1表示背包容量已滿local mp = 0for i = 1, #obj_bag.obj_list doif((obj_bag.obj_list[i].status == 0) and obj_bag.obj_list[i].price > mp) thenmp = obj_bag.obj_list[i].priceindex = iendendreturn index endlocal function greedy_algo(bag, spFunc)local idx = nillocal ntc = 0 -- 已用重量idx = spFunc(bag, ntc)while(idx ~= -1) doif(ntc + bag.obj_list[idx].weight) <= bag.totalC thenbag.obj_list[idx].status = 1ntc = ntc + bag.obj_list[idx].weightelsebag.obj_list[idx].status = 2endidx = spFunc(bag, ntc)endprint("==============11111")dump(bag.obj_list) endlocal bag_1 = {obj_list = {{weight = 10, price = 10, status = 0},{weight = 20, price = 20, status = 0},{weight = 30, price = 40, status = 0},{weight = 40, price = 30, status = 0},{weight = 50, price = 50, status = 0},{weight = 60, price = 70, status = 0},},totalC = 150 }greedy_algo(bag_1, choose_func1)

?

總結

貪婪法只能得到比較接近最優解的近似最優解，但是作為一種啟發式輔助方法在很多算法中都得到了廣泛的應用，很多常用的算法在解決局部最優決策時，都會應用到貪婪法。比如 Dijkstra 的單源最短路徑算法在從 dist 中選擇當前最短距離的節點時，就是采用的貪婪法策略。事實上，在任何算法中，只要在某個階段使用了只考慮局部最優情況的選擇策略，都可以理解為使用了貪婪算法。

轉載于:https://www.cnblogs.com/orxx/p/10940389.html

總結

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

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