貪心算法（Greedy Algorithm) 簡介貪心算法，又名貪婪法，是尋找最優(yōu)解問題的常用方法，這種方法模式一般將求解過程分成若干個(gè)步驟，但每個(gè)步驟都應(yīng)用貪心原則，選取當(dāng)前狀態(tài)下最好/最優(yōu)的選擇（局部最有利的選擇），并以此希望最后堆疊出的結(jié)果也是最好/最優(yōu)的解。{看著這個(gè)名字，貪心，貪婪這兩字的內(nèi)在含義最為關(guān)鍵。這就好像一個(gè)貪婪的人，他事事都想要眼前看到最好的那個(gè)，看不到長遠(yuǎn)的東西，也不為最終的結(jié)果和將來著想，貪圖眼前局部的利益最大化，有點(diǎn)走一步看一步的感覺。}
步驟1：從某個(gè)初始解出發(fā)；
步驟2：采用迭代的過程，當(dāng)可以向目標(biāo)前進(jìn)一步時(shí)，就根據(jù)局部最優(yōu)策略，得到一部分解，縮小問題規(guī)模；
步驟3：將所有解綜合起來。
事例一：找零錢問題假設(shè)你開了間小店，不能電子支付，錢柜里的貨幣只有 25 分、10 分、5 分和 1 分四種硬幣，如果你是售貨員且要找給客戶 41 分錢的硬幣，如何安排才能找給客人的錢既正確且硬幣的個(gè)數(shù)又最少？這里需要明確的幾個(gè)點(diǎn)：1.貨幣只有 25 分、10 分、5 分和 1 分四種硬幣；2.找給客戶 41 分錢的硬幣；3.硬幣最少化思考，能使用我們今天學(xué)到的貪婪算法嗎？怎么做？（回顧一下上文貪婪法的基本步驟，1，2，3）
找給顧客sum_money=41分錢，可選擇的是25 分、10 分、5 分和 1 分四種硬幣。能找25分的，不找10分的原則，初次先找給顧客25分；
還差顧客sum_money=41-25=16。然后從25 分、10 分、5 分和 1 分四種硬幣選取局部最優(yōu)的給顧客，也就是選10分的，此時(shí)sum_money=16-10=6。重復(fù)迭代過程，還需要sum_money=6-5=1,sum_money=1-1=0。至此，顧客收到零錢，交易結(jié)束；
此時(shí)41分，分成了1個(gè)25，1個(gè)10，1個(gè)5，1個(gè)1，共四枚硬幣。
編程實(shí)現(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;}事例二:背包最大價(jià)值問題有一個(gè)背包，最多能承載重量為 C=150的物品，現(xiàn)在有7個(gè)物品（物品不能分割成任意大?。?，編號為 1~7，重量分別是 wi=[35,30,60,50,40,10,25]，價(jià)值分別是 pi=[10,40,30,50,35,40,30]，現(xiàn)在從這 7 個(gè)物品中選擇一個(gè)或多個(gè)裝入背包，要求在物品總重量不超過 C 的前提下，所裝入的物品總價(jià)值最高。這里需要明確的幾個(gè)點(diǎn)：
每個(gè)物品都有重量和價(jià)值兩個(gè)屬性；
每個(gè)物品分被選中和不被選中兩個(gè)狀態(tài)（后面還有個(gè)問題，待討論）；
可選物品列表已知，背包總的承重量一定。
所以，構(gòu)建描述每個(gè)物品的數(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)體的形式，主要是可以減少代碼的書寫量,可以實(shí)現(xiàn)代碼的復(fù)用性和可擴(kuò)展性,簡化，提高可讀性。就是貪圖簡單方便，規(guī)避繁瑣。
如下,實(shí)例化
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)背包的價(jià)值最大呢？
策略1：價(jià)值主導(dǎo)選擇，每次都選價(jià)值最高的物品放進(jìn)背包；
策略2：重量主導(dǎo)選擇，每次都選擇重量最輕的物品放進(jìn)背包；
策略3：價(jià)值密度主導(dǎo)選擇，每次選擇都選價(jià)值/重量最高的物品放進(jìn)背包。
（貪心法則：求解過程分成若干個(gè)步驟，但每個(gè)步驟都應(yīng)用貪心原則，選取當(dāng)前狀態(tài)下最好的或最優(yōu)的選擇（局部最有利的選擇），并以此希望最后堆疊出的結(jié)果也是最好或最優(yōu)的解）
策略1：價(jià)值主導(dǎo)選擇，每次都選價(jià)值最高的物品放進(jìn)背包根據(jù)這個(gè)策略最終選擇裝入背包的物品編號依次是 4、2、6、5，此時(shí)包中物品總重量是 130，總價(jià)值是 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ù)這個(gè)策略最終選擇裝入背包的物品編號依次是 6、7、2、1、5，此時(shí)包中物品總重量是 140，總價(jià)值是 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：價(jià)值密度主導(dǎo)選擇，每次選擇都選價(jià)值/重量最高(大)的物品放進(jìn)背包物品的價(jià)值密度 si 定義為 pi/wi，這 7 件物品的價(jià)值密度分別為 si=[0.286,1.333,0.5,1.0,0.875,4.0,1.2]。根據(jù)這個(gè)策略最終選擇裝入背包的物品編號依次是 6、2、7、4、1，此時(shí)包中物品的總重量是 150，總價(jià)值是 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;//把這個(gè)idx的物體的重量裝進(jìn)去，計(jì)算當(dāng)前的重量 } else { //不能選這個(gè)物品了，做個(gè)標(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é)果：
但是，我們再回顧一下第一個(gè)事例問題現(xiàn)在問題變了，還是需要找給顧客41分錢，現(xiàn)在的貨幣只有 25 分、20分、10 分、5 分和 1 分四種硬幣；該怎么辦？按照貪心算法的三個(gè)步驟：1.41分，局部最優(yōu)化原則，先找給顧客25分；2.此時(shí)，41-25=16分，還需要找給顧客10分，然后5分，然后1分；3.最終，找給顧客一個(gè)25分，一個(gè)10分，一個(gè)5分，一個(gè)1分，共四枚硬幣。是不是覺得哪里不太對，如果給他2個(gè)20分，加一個(gè)1分，三枚硬幣就可以了呢？_;總結(jié)：貪心算法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡單，高效，省去了為了找最優(yōu)解可能需要窮舉操作，通常作為其它算法的輔助算法來使用；缺點(diǎn)：不從總體上考慮其它可能情況，每次選取局部最優(yōu)解，不再進(jìn)行回溯處理，所以很少情況下得到最優(yōu)解。
