貪心算法實驗求解背包問題

1、算法分析與設(shè)計實驗報告第 四 次實驗姓名學(xué)號班級時間10.17上午地點工訓(xùn)樓309 實驗名稱貪心算法實驗(求解背包問題)實驗?zāi)康耐ㄟ^上機實驗，要求掌握貪心算法的問題描述、算法設(shè)計思想、程序設(shè)計。實驗原理給定任意幾組數(shù)據(jù)，利用貪心算法的思想，將物品裝入背包并使得其價值最大。程序思路：與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1in。（1） 首先將單位重量的平均價值排序。（2） 根據(jù)背包容量依次將平均價值高的物品放入背包中。實驗步驟（1）首先計算每種物品單位重量的價值vi/wi；（2）依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝

2、入背包；（3）若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包；（4）依此策略一直地進(jìn)行下去，直到背包裝滿為止。關(guān)鍵代碼bool comparison(st a,st b) /自定義函數(shù)說明sort函數(shù)使用的模式是從大到小排序 return a.perval>b.perval; void Knapsack(int n,float m,st item,float x)int i;float temN; /該變量數(shù)組用來記錄排好序之后的物品是否被放入背包float tmpN; /定義一個數(shù)組用來保存以前的編號及重量，用于構(gòu)造最優(yōu)解for

3、(i=0;i<n;i+)tmpi=itemi.w;sort(item,item+n,comparison); /實現(xiàn)單位重量的平均價值的物品的排序for(i=0;i<n;i+) /初始化數(shù)組x及temxi=0,temi=0;float c=m;for(i=0;i<n;i+) /物品整件被裝下，則xi=1;if(itemi.w>c)break;temi=1;c-=itemi.w;if(i<n) /物品只有部分被裝下temi=c/itemi.w;for(i=0;i<n;i+) /將排好序的物品編號與原始編號匹配for(int j=0;j<n;j+) /構(gòu)造

4、最優(yōu)解if(itemi.w=tmpj)xj=temi;測試結(jié)果輸入較小的結(jié)果： 輸入較大的結(jié)果： 實驗心得首先這個實驗，需要注意的點是背包問題與0-1背包不同，物品可以部分的放入背包中，所以思路也不一樣，首先就是將物品按照單位質(zhì)量價值排序，只這一點就有一點難度。難度在于要是排序后物品的編號就會發(fā)生改變，輸出的就不是之前的編號的物品，導(dǎo)致錯誤，后來發(fā)現(xiàn)如果為每一個物品保存一個副本，然后將它們的編號進(jìn)行對比，就可以進(jìn)行正確的輸出了。其中這個實驗讓我學(xué)到了兩點：一是結(jié)構(gòu)體的使用，之前一直沒有怎么用過，現(xiàn)在才發(fā)現(xiàn)自己其實不會用；二十對于庫函數(shù)sort函數(shù)的使用。感覺每一次實驗都有學(xué)到東西，很開心。實驗

5、得分助教簽名附錄：完整代碼（貪心法）/貪心算法 背包問題#include<iostream>#include<algorithm>#include<time.h>#include<iomanip>using namespace std;const int N=10000;struct st /定義結(jié)構(gòu)體，用來存放和物品相關(guān)的變量float v;float w;float perval;void Knapsack(int n,float m,st item,float x); /聲明貪心算法求解問題函數(shù)int main()float m; int

6、n,i;cout<<"請輸入背包的容量："cin>>m;cout<<"請輸入物品的個數(shù)："cin>>n;st itemN; float xN+1;cout<<"待裝物品的重量為："<<endl;for(i=0;i<n;i+)cin>>itemi.w;cout<<endl;cout<<"待裝物品的價值為："<<endl;for(i=0;i<n;i+)cin>>itemi.v;

7、cout<<endl;/計算每一個物品的單位重量的價值for(i=0;i<n;i+)itemi.perval=itemi.v/itemi.w;clock_t start,end,over; /計算程序運行時間的算法start=clock();end=clock();over=end-start;start=clock(); Knapsack(n,m,item,x); /調(diào)用貪心算法函數(shù)cout<<"選?擇?裝Á¡ã下?的Ì?物?品¡¤的Ì?比À¨¨例

8、64;y如¨?下?：êo"<<endl; /輸出最優(yōu)解編號及比例for(i=0;i<n;i+)cout<<""<<i+1<<":"<<xi<<endl;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); /顯示運行時間system("pause");return 0; bool comparison(st a,st

9、 b)/自定義函數(shù)說明sort函數(shù)使用的形式是從大到小排序 return a.perval>b.perval; void Knapsack(int n,float m,st item,float x)int i;float temN; /該變量數(shù)組用來記錄排好序之后的物品是否被放入背包float tmpN; /定義一個數(shù)組用來保存以前的編號及重量，用于構(gòu)造最優(yōu)解for(i=0;i<n;i+)tmpi=itemi.w;sort(item,item+n,comparison); /實現(xiàn)單位重量的平均價值的物品的排序for(i=0;i<n;i+) /初始化數(shù)組x及temxi=0,temi=0;float c=m;for(i=0;i<n;i+) /物品整件被裝下，則xi=1;if(itemi.w>c)brea