1.實驗題目
給定n種物品和一個背包。物品i的重量是Wi背包問題的貪心算法c語言，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?
2.實驗目的 掌握貪心算法的基本思想；掌握貪心算法中貪心選擇性質的分析與證明；掌握貪心算法求解問題的方法。 3.實驗要求
(1)根據實驗內容構思設計算法，選取適合的數據結構；
(2)對所設計的算法采用大O符號進行時間復雜性分析；
(3)上機實現算法，編程語言不限；
(4)實驗報告內容應包括問題描述、問題分析、算法設計、算法實現、運行結果及算法復雜度分析等內容。
4.實驗過程
#include 
{
int weight;// the weight of goods重量
int value;// the value of goods價值
double ValPerWei;// value per weight權重
double load; //物品裝入背包的部分的系數（例如上圖中物品全部裝入則load為1，裝入10/20則load為0.5）
};
int cmp( Goods const &a, Goods const &b)//定義sort函數的比較函數
{
if(a.ValPerWei<b.ValPerWei) return 0;
else return 1;
}
void Greedy(Goods g[],int good_num, int content)//貪心算法
{
for(int i=0; i<good_num; i++)
{
if(content>g[i].weight)//如果背包足夠裝下整個物品
{
content-=g[i].weight;
g[i].load=1;
}
else if(content>0){//如果背包不足以裝下整個物品
g[i].load=(double)content/g[i].weight;//計算物品裝入背包的部分
content=0;//背包容量置0
return;//程序結束，返回
}
}
}
int main()
{
int goods_num;
int bagvol;
double total_value=0;
double total_weight=0;
cout<<"Please input the volum of bag:"<<endl;
cin>>bagvol;
cout<<"Please input the number of goods:"<<endl;
cin>>goods_num;
Goods G[goods_num+1];
cout<<"Please input the weight and value of goods:"<<endl;
for(int i=0; i<goods_num; i++)
{
cin>>G[i].weight>>G[i].value;//輸入重量價值
G[i].ValPerWei=(double)G[i].value/G[i].weight;//計算權重
G[i].load=0;//load置0
}
sort (G,G+goods_num,cmp);//sort by ValPerWei
Greedy(G,goods_num,bagvol);
cout<<"Info of loaded goods:"<<endl;
for(int i=0;i<goods_num;i++)//output the info of goods
{
if(G[i].load==0.0)break;//如果檢測到物品未被裝入背包，則推出循環
total_value+=(G[i].value*G[i].load);//裝入背包的物品總價值
total_weight+=(G[i].weight*G[i].load);//裝入背包的物品總重量
cout<<"weight: "<<G[i].weight<<" "<<"value: "<<G[i].value<<" "<<"the value per weight of good: "<<G[i].ValPerWei<<" the part of goods: "<<G[i].load<<endl;//輸出裝入背包的物品信息
}
cout<<"the volum of bag is: "<<bagvol<<endl;//輸出背包容量
cout<<"the total weight is: "<<total_weight<<endl;//輸出裝入物品的總重量
cout<<"the total value is: "<<total_value<<endl;//輸出裝入物品的總價值
}
5.運行結果
6.實驗分析
通過這次實驗，我較為透徹的理解了貪心算法的基本思想和幾個基本步驟，而且進一步提高了自己的自學能力和編程能力。在求解背包問題中，關鍵是三種貪心策略的設計。貪心算法求解問題一般具有兩個重要性質：貪心選擇性質和最優子結構性質。雖然貪心算法能盡可能快的求得更好的解背包問題的貪心算法c語言，但也存在一些局限性，例如不能保證求得最終的解是最佳的，不能用來求最大最小解問題，只能滿足某些約束條件的可行解的范圍。