2.1 適用場景
貪婪算法常用於尋求最優解問題。將問題分成若干個求解步驟，在每個步驟中都依據某個最優原則選擇當前狀態的最優解，以此希望最後得到的結果也是最優的。貪婪算法在迭代完一輪之後就不再進行回溯，簡單高效，這種只關注當前狀態最優解的方法，通常可能會錯過全局最優解。
2.2 設計思想
（1）定義最優解模型：將問題抽象為數學模型；
（2）定義子問題最優解結構：將問題分解為若干個子問題；
（3）應用貪婪法則確定每個子問題的最優解，最後得到全局最優解。
2.3 0-1背包問題
總共有7件物品、一個最大承載重量為150的背包，其中每件物品的重量與價格分別為W[i]和P[i]，W=[35,30,60,50,40,10,25],P=[10,40,30,50,35,40,30]；選擇哪些物品裝入背包可以使背包中物品價格最高。
3. C++實現
背包問題可以簡述為：
第1次迭代：背包載重為C，此時所有物品均可選擇，根據貪婪法則選擇一個物品裝入背包，假設選擇了物品i；
第2次迭代：背包載重為C-W[i]，從所有可選物品中根據貪婪法則選擇一個物品裝入背包；
……
第N次迭代：背包不能再裝下物品或者所有物品已被選中，結束算法。
3.1 定義物品數據結構
物品包含三個屬性，重量、價格以及物品狀態，物品狀態0表示該物品未被選擇，1表示已被選擇，2表示在某次迭代中選擇該物品會超過背包允許最大載重，後續也不要再選。
typedef struct
{
int weight;
int price;
int status;
}Object;
3.2 定義背包問題
typedef struct
{
std::vector<Object> objs;
int totalC;
}Knapsack_problem;
3.3 貪婪法則
3.3.1 選擇價格最高的物品
int Choosefunc1(std::vector<Object>& objs)
{
int index = -1;
int maxPrice = 0;
for (int i = 0; i < static_cast<int>(objs.size()); i++)
{
if ((objs[i].status == 0) && (objs[i].price > maxPrice))
{
maxPrice = objs[i].price;
index = i;
}
}
return index;
}
3.3.2 選擇重量最輕的物品
int Choosefunc2(std::vector<Object>& obj)
{
int index = -1;
int minWeight = 10000;
for (int i = 0; i < static_cast<int>(obj.size()); i++)
{
if (obj[i].status == 0 && obj[i].weight < minWeight)
{
minWeight = obj[i].weight;
index = i;
}
}
return index;
}
3.3.3 選擇價格密度最高的物品
int Choosefunc3(std::vector<Object>& obj)
{
int index = -1;
double maxDes = 0.0;
for (int i = 0; i < static_cast<int>(obj.size()); i++)
{
if (obj[i].status == 0)
{
double si = obj[i].price/obj[i].weight;
if (si > maxDes)
{
maxDes = si;
index = i;
}
}
}
return index;
}
3.4 輔助函數
列印最終所選物品的重量以及價格：
void PrintResult(std::vector<Object>& objs)
{
int totalW = 0;
int totalP = 0;
for (int i = 0; i < static_cast<int>(objs.size()); i++)
{
if (objs[i].status == 1)
{
totalW += objs[i].weight;
totalP += objs[i].price;
cout<<"物品"<<i<<": 重量="<<objs[i].weight<<", 價格="<<objs[i].price<<endl;
}
}
cout<<"所選物品總重:"<<totalW<<", 總價格:"<<totalP<<endl;
}
v
3.5 貪婪算法
typedef int (*Select_policy)(std::vector<Object>& objs);
void GreedyAlgorithm(Knapsack_problem* instance, Select_policy spFunc)
{
int index;
int mCurWeight = 0;
while((index = spFunc(instance->objs)) != -1)
{
if (mCurWeight + instance->objs[index].weight <= instance->totalC)
{
instance->objs[index].status = 1;
mCurWeight += instance->objs[index].weight;
}
else
{
instance->objs[index].status = 2;
}
}
PrintResult(instance->objs);
}
3.6 算法測試
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
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(int argc, char const *argv[])
{
Knapsack_problem instance;
instance.objs.assign(objects, objects+7);
instance.totalC = 150;
GreedyAlgorithm(&instance, Choosefunc1);
return 0;
}
測試結果
物品1: 重量=30, 價格=40
物品3: 重量=50, 價格=50
物品4: 重量=40, 價格=35
物品5: 重量=10, 價格=40
所選物品總重:130, 總價格:165
4. Python實現
class Knapsack_problem():
def __init__(self, weight, price, totalC):
self.weight = weight
self.price = price
self.number = len(weight)
self.status = [0]*self.number
self.totalC = totalC
def PrintResult(self):
totalW = 0
totalP = 0
for i in range(self.number):
if self.status[i] == 1:
totalW += self.weight[i]
totalP += self.price[i]
print('所選物品：%d, 重量：%d, 價格:%d' % (i, self.weight[i], self.price[i]))
print('所選物品總重: %d, 總價值: %d' % (totalW, totalP))
def GreedyAlgorithm(self):
nCurWeight = 0
while True:
idx = self.ChooseFunc1()
if idx == -1:
break
if nCurWeight + self.weight[idx] <= self.totalC:
self.status[idx] = 1
nCurWeight += self.weight[idx]
else:
self.status[idx] = 2
self.PrintResult()
def ChooseFunc1(self):
maxPrice = 0
index = -1
for i in range(self.number):
if (self.status[i] == 0) and (self.price[i] > maxPrice):
maxPrice = self.price[i]
index = i
return index
def ChooseFunc2(self):
minWight = 10000
index = -1
for i in range(self.number):
if (self.status[i] == 0) and (self.weight[i] < minWight):
minWight = self.weight[i]
index = i
return index
def ChooseFunc3(self):
index = -1
maxDensity = 0
for i in range(self.number):
if self.status[i] == 0:
den = self.price[i]/self.weight[i]
if den > maxDensity:
maxDensity = den
index = i
return index
if __name__ == '__main__':
weight = [35, 30, 60, 50, 40, 10, 25]
price = [10, 40, 30, 50, 35, 40, 30]
totalC = 150
instance = Knapsack_problem(weight, price, totalC)
instance.GreedyAlgorithm()
測試結果：
所選物品：1, 重量：30, 價格:40
所選物品：3, 重量：50, 價格:50
所選物品：4, 重量：40, 價格:35
所選物品：5, 重量：10, 價格:40
所選物品總重: 130, 總價值: 165
5. 小結
在某個階段中只考慮局部最優解都可以理解為貪婪算法，貪婪算法的解通常只能接近全局最優解。