背包问题贪心算法

1、算法分析与设计实验报告第4次实验姓名学号班级时间11.14下午地点四合院实验名称贪心算法实验（求解背包问题）实验目的.通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。.设计程序，利用贪心算法求解背包问题，输出相应结果，笄计算出程序运行 所需要的时间。实验原理给定几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。实验步骤计算每种物品单位重量的价值Vi/Wi.依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。关键

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通过这次实验，我回顾了贪心算法实现背包问题，在其中加入了舍伍德随机化过程得到物品的价格和重量，取值更加均匀，让我熟悉了随

5、机化算法， 使结果更可靠。贪心算法与动态规划有所不同， 贪心算法要求每一步的选择都是当前最优 的解，刚开始时，我编写的代码选择的是选择物品中价值最高的，后来发现忽实验心得视了重量，更改后每一步的最优解应该是选择单位重量中价值最高的物品。另外由于需要改进的地方:1,价重比排序中可以选择其他的排序方法降低复杂度。.排序后输出时可以将重量和价格同时输出，即可减少一个循环。.对于随机取数时，出现重量为 0的情况不符合现实，可以改进。实验得分助教签名附录：完整代码#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请输入物品个数：scanf(%d,&M);node NodeM;srand(time=NULL);for(