貪心算法背包問題

1、算法設(shè)計與分析實(shí)驗(yàn)報告2015-2016年第2學(xué)期實(shí)驗(yàn)班級：學(xué)生姓名：學(xué) 號：指導(dǎo)老師：信息工程學(xué)院實(shí)驗(yàn)項目名稱：貪心算法背包問題實(shí)驗(yàn)日期：2016年4月12日一、實(shí)驗(yàn)類型：口驗(yàn)證性口設(shè)計性二、實(shí)驗(yàn)?zāi)康?、掌握背包問題的算法2、初步掌握貪心算法三、實(shí)驗(yàn)內(nèi)容及要求問題描述：與0-1背包問題相似，給定n種物品和一個背包。物品i的重量是wi,其價值為vi,背包的容量為c。與0-1背包問 題不同的是，在選擇物品i裝入背包時，背包問題的解決可以選 擇物品i的一部分，而不一定要全部裝入背包，1 i n。四、實(shí)驗(yàn)步驟#include iostream.h#include stdio.h#include st

2、ruct stone int name;int weight;/ 物品的剩余重量int weight_t;/ 物品的重量float benefit;/物品的價值/float b;void sort(stone *data,int num)if(num1)return;int low=0,high=num;stone key_s=datalow;float key=(float)key_s.benefit/key_s.weight;int empty=low;while(lowhigh) if(low=empty) while(datahigh.benefit/datahigh.weightlo

3、w) high-;if(datahigh.benefit/datahigh.weight=key) datalow=datahigh;empty=high;else if(high=empty) while(datalow.benefit/datalow.weight=key)&(lowh igh) low+; if(datalow.benefit/datalow.weight1)sort(data,empty-1);if(num-empty-10)sort(data+empty+1,num-empty-1);void inputstone(stone *bag,int num) for(in

4、t i=0;inum;i+) =i+1;printf(請輸入第后物品的重量:,i+1);scanf(%d”,&bagi.weight);if (bagi.weight=0)printf( 物品的重量必須大于0!n); printf(請輸入第后物品的價值:,i+1);scanf(%f,&bagi.benefit);if (bagi.benefit=0)printf( 物品的價值必須大于0!n); bagi.weight_t=bagi.weight; int main(int argc, char* argv) int i;int num=0;int weight=0;float

5、 benefit=0;stone *bag; do printf(請輸入背包可容納的重量：)；scanf(%d,&weight);if (weight=0)printf(背包可容納的重量必須大于0!n);while(weight=0); do printf(請輸入物品的數(shù)量:);scanf(%d,&num);if (num=0) printf(物品數(shù)量必須大于0!n);while(num=0);bag=new stonenum;inputstone(bag,num);sort(bag,num-1);for(i=0;i0;i+) stone *temp=bag+i;if(weight=temp-

6、weight) weight-=temp-weight;temp-weight=0;benefit+=temp-benefit;continue;else temp-weight-=weight;weight=0;benefit+=(temp-benefit*(1-(float)temp-weight/temp-we ight_t);break; printf(物品種類放入的比例每單位效益n);for(i=0;iname);printf(tt%.2ftt,(temp-weight_t-temp-weight)/(fl oat)temp-weight_t);printf( %.4fn,temp-

7、benefit/(float)temp-weight_t);printf(總效益:.2f,benefit);delete bag;getchar();system(PAUSE);return EXIT_SUCCESS;return 0;)五、實(shí)驗(yàn)結(jié)果1、實(shí)驗(yàn)圖形1=812，“415位itfitu a輻口囂口囂口艇 廣俞號號號口曹號短 112 2 3 31.777815。即IBe0a明意 - 二 1 1 1任Ru 人入AJ入與入人人種一 請富正揩請請請物啰替品口囂W;5：L6涅塾算蘇野十1匕算法計立0O*七:201沅幅算法的必bu中算法設(shè)計工*2.37502.麗e1 .61542、結(jié)果分析如上面

8、第一個圖所示當(dāng)輸入背包可容納的重要為21,輸入物品的數(shù)量為3,輸入第1號物品的重量為8,輸入第1號物品的價值為12,輸入第2號物品的重量為9,輸入第2號物品的價值為16, 輸入第3號物品的重量為4,輸入第3號物品的價值為15,則可以 得出總效益為43.00。如上面第一個圖所示當(dāng)輸入背包可容納的重要為 30,輸入物 品的數(shù)量為4,輸入第1號物品的重量為3,輸入第1號物品的價 值為15,輸入第2號物品的重量為6,輸入第2號物品的價值為 12,輸入第3號物品的重量為8,輸入第3號物品的價值為19,輸 入第4號物品的重量為13,輸入第4號物品的價值為21,則可以 得出總效益為67.00。3、實(shí)驗(yàn)總結(jié)及心得體會本次的實(shí)驗(yàn)主要是掌握背包問題的算法，在做本次實(shí)驗(yàn)之前， 自己從課本上找了一些與動態(tài)規(guī)劃、貪心、回溯法、分支限界法的原 理相關(guān)的內(nèi)容來看，不過課本所提供的代碼數(shù)組下標(biāo)一般都是從1開始，而我們輸入的數(shù)據(jù)數(shù)組下標(biāo)默認(rèn)都是從 0開始，所以在參考課本 所提供的代碼的同時，必須結(jié)