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

2、入背包；（3）若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包；（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; /定義一個(gè)數(shù)組用來保存以前的編號(hào)及重量，用于構(gòu)造最優(yōu)解for

3、(i=0;i<n;i+)tmpi=itemi.w;sort(item,item+n,comparison); /實(shí)現(xiàn)單位重量的平均價(jià)值的物品的排序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+) /將排好序的物品編號(hào)與原始編號(hào)匹配for(int j=0;j<n;j+) /構(gòu)造

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

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<<"請(qǐng)輸入背包的容量："cin>>m;cout<<"請(qǐng)輸入物品的個(gè)數(shù)："cin>>n;st itemN; float xN+1;cout<<"待裝物品的重量為："<<endl;for(i=0;i<n;i+)cin>>itemi.w;cout<<endl;cout<<"待裝物品的價(jià)值為："<<endl;for(i=0;i<n;i+)cin>>itemi.v;

7、cout<<endl;/計(jì)算每一個(gè)物品的單位重量的價(jià)值for(i=0;i<n;i+)itemi.perval=itemi.v/itemi.w;clock_t start,end,over; /計(jì)算程序運(yùn)行時(shí)間的算法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)解編號(hào)及比例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); /顯示運(yùn)行時(shí)間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; /定義一個(gè)數(shù)組用來保存以前的編號(hào)及重量，用于構(gòu)造最優(yōu)解for(i=0;i<n;i+)tmpi=itemi.w;sort(item,item+n,comparison); /實(shí)現(xiàn)單位重量的平均價(jià)值的物品的排序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