|
貪心算法（Greedy Algorithm) 簡介貪心算法，又名貪婪法，是尋找最優(yōu)解問題的常用方法，這種方法模式一般將求解過程分成若干個步驟，但每個步驟都應(yīng)用貪心原則，選取當(dāng)前狀態(tài)下最好/最優(yōu)的選擇（局部最有利的選擇），并以此希望最后堆疊出的結(jié)果也是最好/最優(yōu)的解。{看著這個名字，貪心，貪婪這兩字的內(nèi)在含義最為關(guān)鍵。這就好像一個貪婪的人，他事事都想要眼前看到最好的那個，看不到長遠(yuǎn)的東西，也不為最終的結(jié)果和將來著想，貪圖眼前局部的利益最大化，有點(diǎn)走一步看一步的感覺。} 貪婪法的基本步驟：步驟1：從某個初始解出發(fā)； 步驟2：采用迭代的過程，當(dāng)可以向目標(biāo)前進(jìn)一步時，就根據(jù)局部最優(yōu)策略，得到一部分解，縮小問題規(guī)模； 步驟3：將所有解綜合起來。 事例一：找零錢問題假設(shè)你開了間小店，不能電子支付，錢柜里的貨幣只有 25 分、10 分、5 分和 1 分四種硬幣，如果你是售貨員且要找給客戶 41 分錢的硬幣，如何安排才能找給客人的錢既正確且硬幣的個數(shù)又最少？這里需要明確的幾個點(diǎn)：1.貨幣只有 25 分、10 分、5 分和 1 分四種硬幣；2.找給客戶 41 分錢的硬幣；3.硬幣最少化思考，能使用我們今天學(xué)到的貪婪算法嗎？怎么做？（回顧一下上文貪婪法的基本步驟，1，2，3）
編程實現(xiàn) #include<iostream>using namespace std;#define ONEFEN 1#define FIVEFEN 5#define TENFEN 10#define TWENTYFINEFEN 25int main(){ int sum_money=41; int num_25=0,num_10=0,num_5=0,num_1=0; //不斷嘗試每一種硬幣 while(money>=TWENTYFINEFEN) { num_25++; sum_money -=TWENTYFINEFEN; } while(money>=TENFEN) { num_10++; sum_money -=TENFEN; } while(money>=FIVEFEN) { num_5++; sum_money -=FIVEFEN; } while(money>=ONEFEN) { num_1++; sum_money -=ONEFEN; } //輸出結(jié)果 cout<< '25分硬幣數(shù)：'<<num_25<<endl; cout<< '10分硬幣數(shù)：'<<num_10<<endl; cout<< '5分硬幣數(shù)：'<<num_5<<endl; cout<< '1分硬幣數(shù)：'<<num_1<<endl; return 0;}事例二:背包最大價值問題有一個背包，最多能承載重量為 C=150的物品，現(xiàn)在有7個物品（物品不能分割成任意大?。幪枮?1~7，重量分別是 wi=[35,30,60,50,40,10,25]，價值分別是 pi=[10,40,30,50,35,40,30]，現(xiàn)在從這 7 個物品中選擇一個或多個裝入背包，要求在物品總重量不超過 C 的前提下，所裝入的物品總價值最高。這里需要明確的幾個點(diǎn)：
所以，構(gòu)建描述每個物品的數(shù)據(jù)體結(jié)構(gòu) OBJECT和背包問題定義為 //typedef是類型定義的意思//定義待選物體的結(jié)構(gòu)體類型typedef struct tagObject{ int weight; int price; int status;}OBJECT;//定義背包問題typedef struct tagKnapsackProblem{ vector<OBJECT>objs; int totalC;}KNAPSACK_PROBLEM;這里采用定義結(jié)構(gòu)體的形式，主要是可以減少代碼的書寫量,可以實現(xiàn)代碼的復(fù)用性和可擴(kuò)展性,簡化，提高可讀性。就是貪圖簡單方便，規(guī)避繁瑣。 如下,實例化 objectsOBJECT objects[] = { { 35,10,0 },{ 30,40,0 },{ 60,30,0 },{ 50,50,0 }, { 40,35,0 },{ 10,40,0 },{ 25,30,0 } };思考：如何選，才使得裝進(jìn)背包的價值最大呢？ 策略1：價值主導(dǎo)選擇，每次都選價值最高的物品放進(jìn)背包； 策略2：重量主導(dǎo)選擇，每次都選擇重量最輕的物品放進(jìn)背包； 策略3：價值密度主導(dǎo)選擇，每次選擇都選價值/重量最高的物品放進(jìn)背包。 （貪心法則：求解過程分成若干個步驟，但每個步驟都應(yīng)用貪心原則，選取當(dāng)前狀態(tài)下最好的或最優(yōu)的選擇（局部最有利的選擇），并以此希望最后堆疊出的結(jié)果也是最好或最優(yōu)的解） 策略1：價值主導(dǎo)選擇，每次都選價值最高的物品放進(jìn)背包根據(jù)這個策略最終選擇裝入背包的物品編號依次是 4、2、6、5，此時包中物品總重量是 130，總價值是 165。 //遍歷沒有被選的objs,并且選擇price最大的物品,返回被選物品的編號int Choosefunc1(std::vector<OBJECT>& objs, int c){ int index = -1; //-1表示背包容量已滿 int max_price = 0; //在objs[i].status == 0的物品里，遍歷挑選objs[i].price最大的物品 for (int i = 0; i < static_cast<int>(objs.size()); i++) { if ((objs[i].status == 0) && (objs[i].price > max_price ))//objs沒有被選,并且price> max_price { max_price = objs[i].price; index = i; } } return index;}策略2：重量主導(dǎo)選擇，每次都選擇重量最輕(小)的物品放進(jìn)背包根據(jù)這個策略最終選擇裝入背包的物品編號依次是 6、7、2、1、5，此時包中物品總重量是 140，總價值是 155。 int Choosefunc2(std::vector<OBJECT>& objs, int c){ int index = -1; int min_weight= 10000; for (int i = 0; i < static_cast<int>(objs.size()); i++) { if ((objs[i].status == 0) && (objs[i].weight < min_weight)) { min_weight= objs[i].weight; index = i; } } return index;}策略3：價值密度主導(dǎo)選擇，每次選擇都選價值/重量最高(大)的物品放進(jìn)背包物品的價值密度 si 定義為 pi/wi，這 7 件物品的價值密度分別為 si=[0.286,1.333,0.5,1.0,0.875,4.0,1.2]。根據(jù)這個策略最終選擇裝入背包的物品編號依次是 6、2、7、4、1，此時包中物品的總重量是 150，總價值是 170。 int Choosefunc3(std::vector<OBJECT>& objs, int c){ int index = -1; double max_s = 0.0; for (int i = 0; i < static_cast<int>(objs.size()); i++) { if (objs[i].status == 0) { double si = objs[i].price; si = si / objs[i].weight; if (si > max_s) { max_s = si; index = i; } } } return index;}有了物品，有了方法，下面就是將兩者結(jié)合起來的貪心算法 GreedyAlgovoid GreedyAlgo(KNAPSACK_PROBLEM *problem, SELECT_POLICY spFunc){ int idx; int sum_weight_current = 0; //先選 while ((idx = spFunc(problem->objs, problem->totalC- sum_weight_current)) != -1) { //再檢查，是否能裝進(jìn)去 if ((sum_weight_current + problem->objs[idx].weight) <= problem->totalC) { problem->objs[idx].status = 1;//如果背包沒有裝滿，還可以再裝,標(biāo)記下裝進(jìn)去的物品狀態(tài)為1 sum_weight_current += problem->objs[idx].weight;//把這個idx的物體的重量裝進(jìn)去，計算當(dāng)前的重量 } else { //不能選這個物品了，做個標(biāo)記2后重新選剩下的 problem->objs[idx].status = 2; } } PrintResult(problem->objs);//輸出函數(shù)的定義，查看源代碼}注意：這里對objs[idx].status定義了三種狀態(tài)，分別是待選擇為0（初始所有狀態(tài)均為0），裝進(jìn)包里變?yōu)?，判斷不符合變?yōu)?，這樣最后只需要拿去狀態(tài)為1的即可。主函數(shù)部分 OBJECT objects[] = { { 35,10,0 },{ 30,40,0 },{ 60,30,0 },{ 50,50,0 }, { 40,35,0 },{ 10,40,0 },{ 25,30,0 } };int main(){ KNAPSACK_PROBLEM problem; problem.objs.assign(objects, objects + 7);//assign賦值，std::vector::assign problem.totalC = 150; cout << 'Start to find the best way ,NOW' << endl; GreedyAlgo(&problem, Choosefunc3); system('pause'); return 0;}查看策略3的輸出結(jié)果：  但是，我們再回顧一下第一個事例問題現(xiàn)在問題變了，還是需要找給顧客41分錢，現(xiàn)在的貨幣只有 25 分、20分、10 分、5 分和 1 分四種硬幣；該怎么辦？按照貪心算法的三個步驟：1.41分，局部最優(yōu)化原則，先找給顧客25分；2.此時，41-25=16分，還需要找給顧客10分，然后5分，然后1分；3.最終，找給顧客一個25分，一個10分，一個5分，一個1分，共四枚硬幣。是不是覺得哪里不太對，如果給他2個20分，加一個1分，三枚硬幣就可以了呢？_;總結(jié)：貪心算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡單，高效，省去了為了找最優(yōu)解可能需要窮舉操作，通常作為其它算法的輔助算法來使用；缺點(diǎn)：不從總體上考慮其它可能情況，每次選取局部最優(yōu)解，不再進(jìn)行回溯處理，所以很少情況下得到最優(yōu)解。 |
|
|
