背包問題貪心算法

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

2、代碼/按價重比冒泡排序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(物品的價重比從高到低依次排列為：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選中物品的價格為：n);for(i=0;iM;i+)if(Nodei.weight+curweight).00 B. 00 8. 00進中物品的價格為第1次選擇后，價格為；7. 00露2次山罩后，價格為，1620案2次選擇后，價格為：23.00SU ser ss (nmyDes ktop01 國問意 “一口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口物品的價格為:次選擇后, 次選擇后, 次選擇后, 次選擇后, 次選擇后,次選擇后 次選擇后, 次選擇后, 次選擇后,tni iT1政選擇后，價格為1次選擇后.價格為2次選擇后，偷格為價格為： 價格為: 林榕為C 疥格為: 價格為: 杯格為: 價格為; 彳介榕為; 彳介格為I2.宛g. ao16. 0020. 0028. 0085. 0039. 0047. 0053.00：60. 00t 6&. 00二 65. 00通過這次實驗，我回顧了貪心算法實現(xiàn)背包問題，在其中加入了舍伍德隨機化過程得到物品的價格和重量，取值更加均勻，讓我熟悉了隨

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

6、lue,curvalue=0;float Weight,curweight=0;/按價重比冒泡排序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(物品的價重比從高到低依次排列為：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請輸入背包容積：scanf(%f,&Weight);printf(n請輸入物品個數(shù)：scanf(%d,&M);node NodeM;srand(time=NULL);for(