貪心算法，又名貪婪算法，顧名思義，是指在對問題求解時，總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。

貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態以前的過程不會影響以后的狀態，只與當前狀態有關。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。如單源最短路經問題，最小生成樹問題，背包最大價值問題等。在一些情況下，即使貪心算法不能得到整體最優解，其最終結果卻是最優解的很好近似。

這里我們采用更容易理解的背包最大價值問題：

有一個背包，最多能承載重量為 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.可選物品列表已知，背包總的承重量一定。所以，構建描述每個物品的數據體結構 OBJECT和背包問題定義為：//typedef是類型定義的意思

//定義待選物體的結構體類型
typedef struct tagObject
{
????int weight;
????int price;
????int status;
}OBJECT;

//定義背包問題
typedef struct tagKnapsackProblem
{
????vector<OBJECT>objs;
????int totalC;
}KNAPSACK_PROBLEM;

如下,實例化objectsOBJECT objects[] = { { 35,10,0 },{ 30,40,0 },{ 60,30,0 },{ 50,50,0 },

                    { 40,35,0 },{ 10,40,0 },{ 25,30,0 } };

那么，我們思考一下，如何選，才使得裝進背包的價值最大呢？

策略1：價值主導選擇，每次都選價值最高的物品放進背包；

策略2：重量主導選擇，每次都選擇重量最輕的物品放進背包；

策略3：價值密度主導選擇，每次選擇都選價值/重量最高的物品放進背包。

策略1：價值主導選擇

每次都選價值最高的物品放進背包根據這個策略最終選擇裝入背包的物品編號依次是 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：重量主導選擇

每次都選擇重量最輕(小)的物品放進背包根據這個策略最終選擇裝入背包的物品編號依次是 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：價值密度主導選擇

每次選擇都選價值/重量最高(大)的物品放進背包物品的價值密度 si 定義為 pi/wi，這 7 件物品的價值密度分別為 si=[0.286,1.333,0.5,1.0,0.875,4.0,1.2]。根據這個策略最終選擇裝入背包的物品編號依次是 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;
}

回過頭來，我們再來根據貪心算法的定義來對這個問題進行貪心算法GreedyAlgo：

void 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)
????{ ??//再檢查，是否能裝進去
????????if ((sum_weight_current + problem->objs[idx].weight) <= problem->totalC)
????????{
????????????problem->objs[idx].status = 1;//如果背包沒有裝滿，還可以再裝,標記下裝進去的物品狀態為1
????????????sum_weight_current += problem->objs[idx].weight;//把這個idx的物體的重量裝進去，計算當前的重量
????????}
????????else
????????{
????????????//不能選這個物品了，做個標記2后重新選剩下的
????????????problem->objs[idx].status = 2;
????????}
????}
????PrintResult(problem->objs);//輸出函數的定義，查看源代碼
}

主函數部分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的輸出結果：

通過上面的背包價值最大問題，我們不難看出：貪心算法總體來說簡單，高效，省去了為了找最優解可能需要窮舉操作，通常作為其它算法的輔助算法來使用；但貪心算法不從總體上考慮其它可能情況，每次選取局部最優解，不再進行回溯處理，所以很少情況下得到最優解。貪心算法只是眾多優秀算法中的一員，想要了解更多神奇的算法可以觀看本站的數據結構和算法教程，學習新的算法知識。