背包問(wèn)題貪心算法

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第4次實(shí)驗(yàn)姓名學(xué)號(hào)班級(jí)時(shí)間11.14下午地點(diǎn)四合院實(shí)驗(yàn)名稱貪心算法實(shí)驗(yàn)（求解背包問(wèn)題）實(shí)驗(yàn)?zāi)康?通過(guò)上機(jī)實(shí)驗(yàn)，要求掌握貪心算法的問(wèn)題描述、算法設(shè)計(jì)思想、程序設(shè)計(jì)。.設(shè)計(jì)程序，利用貪心算法求解背包問(wèn)題，輸出相應(yīng)結(jié)果，笄計(jì)算出程序運(yùn)行 所需要的時(shí)間。實(shí)驗(yàn)原理給定幾組數(shù)據(jù)，利用貪心算法的思想，將物品裝入背包并使得其價(jià)值最大。實(shí)驗(yàn)步驟計(jì)算每種物品單位重量的價(jià)值Vi/Wi.依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C,則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。關(guān)鍵

2、代碼/按價(jià)重比冒泡排序void sort(node Node,int M)int i,j;node temp;for(i=0;iM-1;i+)for(j=i+1;jM;j+)if(Nodei.value/(float)Nodei.weight)Nodej.value/(float)Node j.weight)temp=Nodei;Nodei=Nodej;Nodej=temp;printf(物品的價(jià)重比從高到低依次排列為：n);for(i=0;iM;i+)printf(%.2f ,Nodei.value);printf(n);for(i=0;iM;i+)printf(%.2f ,Nodei.we

3、ight);/裝包主要方法及輸出void pack(node Node,int M)int i,j=1;printf(nn選中物品的價(jià)格為：n);for(i=0;iM;i+)if(Nodei.weight+curweight).00 B. 00 8. 00進(jìn)中物品的價(jià)格為第1次選擇后，價(jià)格為；7. 00露2次山罩后，價(jià)格為，1620案2次選擇后，價(jià)格為：23.00SU ser ss (nmyDes ktop01 國(guó)問(wèn)意 “一口2.7.瓦7,7. 005 004. 001. 0C3, 00& 0C7. 0。6, 0Ooogoo00oogooooDO 3 8go o2.o o 6.o o6.o o

4、 3.15 8o o o o o o 7 7 70 15 7口物品的價(jià)格為:次選擇后, 次選擇后, 次選擇后, 次選擇后, 次選擇后,次選擇后 次選擇后, 次選擇后, 次選擇后,tni iT1政選擇后，價(jià)格為1次選擇后.價(jià)格為2次選擇后，偷格為價(jià)格為： 價(jià)格為: 林榕為C 疥格為: 價(jià)格為: 杯格為: 價(jià)格為; 彳介榕為; 彳介格為I2.宛g. ao16. 0020. 0028. 0085. 0039. 0047. 0053.00：60. 00t 6&. 00二 65. 00通過(guò)這次實(shí)驗(yàn)，我回顧了貪心算法實(shí)現(xiàn)背包問(wèn)題，在其中加入了舍伍德隨機(jī)化過(guò)程得到物品的價(jià)格和重量，取值更加均勻，讓我熟悉了隨

5、機(jī)化算法， 使結(jié)果更可靠。貪心算法與動(dòng)態(tài)規(guī)劃有所不同， 貪心算法要求每一步的選擇都是當(dāng)前最優(yōu) 的解，剛開始時(shí)，我編寫的代碼選擇的是選擇物品中價(jià)值最高的，后來(lái)發(fā)現(xiàn)忽實(shí)驗(yàn)心得視了重量，更改后每一步的最優(yōu)解應(yīng)該是選擇單位重量中價(jià)值最高的物品。另外由于需要改進(jìn)的地方:1,價(jià)重比排序中可以選擇其他的排序方法降低復(fù)雜度。.排序后輸出時(shí)可以將重量和價(jià)格同時(shí)輸出，即可減少一個(gè)循環(huán)。.對(duì)于隨機(jī)取數(shù)時(shí)，出現(xiàn)重量為 0的情況不符合現(xiàn)實(shí)，可以改進(jìn)。實(shí)驗(yàn)得分助教簽名附錄：完整代碼#include #include #include struct nodefloat value;float weight;float Va

6、lue,curvalue=0;float Weight,curweight=0;/按價(jià)重比冒泡排序void sort(node Node口,int M)int i,j;node temp;for(i=0;iM-1;i+)for(j=i+1;jM;j+)if(Nodei.value/(float)Nodei.weight)Nodej.value/(float)Nodej.weight)temp=Nodei;Nodei=Nodej;Nodej=temp;printf(物品的價(jià)重比從高到低依次排列為：n);for(i=0;iM;i+)printf(%.2f ,Nodei.value);printf(

7、n);for(i=0;iM;i+)printf(%.2f ,Nodei.weight);/裝包主要方法及輸出void pack(node Node,int M)int i,j=1;printf(nn選中物品的彳格為：n);for(i=0;iM;i+)if(Nodei.weight+curweight)=Weight)curvalue+=Nodei.value;curweight+=Nodei.weight;printf(第j次選擇為:j+；)int main()int i,M;printf(n請(qǐng)輸入背包容積：scanf(%f,&Weight);printf(n請(qǐng)輸入物品個(gè)數(shù)：scanf(%d,&M);node NodeM;srand(time=NULL);for(