背包问题(贪心算法)

算法分析与设计实验报告第4次实验姓名学号班级时间11.14下午地点四合院实验名称贪心算法实验（求解背包问题）实验目的1.通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。2.设计程序，利用贪心算法求解背包问题，输出相应结果，并计算出程序运行所需要的时间。实验原理给定几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。实验步骤①计算每种物品单位重量的价值Vi/Wi.②依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。③若将这种物品全部装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并尽可能多地装入背包。④依此策略一直地进行下去，直到背包装满为止。关键代码//按价重比冒泡排序voidsort(nodeNode[],intM){inti,j;nodetemp;for(i=0;iM-1;i++){for(j=i+1;jM;j++){if((Node[i].value/(float)Node[i].weight)Node[j].value/(float)Node[j].weight){temp=Node[i];Node[i]=Node[j];Node[j]=temp;}}}printf(物品的价重比从高到低依次排列为：\n);for(i=0;iM;i++){printf(%.2f,Node[i].value);}printf(\n);for(i=0;iM;i++){printf(%.2f,Node[i].weight);}}//装包主要方法及输出voidpack(nodeNode[],intM){inti,j=1;printf(\n\n选中物品的价格为：\n);for(i=0;iM;i++){if((Node[i].weight+curweight)=Weight){curvalue+=Node[i].value;curweight+=Node[i].weight;printf(第j次选择为：%.2f\n,curvalue);j++;}}}测试结果实验心得通过这次实验，我回顾了贪心算法实现背包问题，在其中加入了舍伍德随机化过程得到物品的价格和重量，取值更加均匀，让我熟悉了随机化算法，使结果更可靠。贪心算法与动态规划有所不同，贪心算法要求每一步的选择都是当前最优的解，刚开始时，我编写的代码选择的是选择物品中价值最高的，后来发现忽视了重量，更改后每一步的最优解应该是选择单位重量中价值最高的物品。另外由于需要改进的地方：1.价重比排序中可以选择其他的排序方法降低复杂度。2.排序后输出时可以将重量和价格同时输出，即可减少一个循环。3.对于随机取数时，出现重量为0的情况不符合现实，可以改进。实验得分助教签名附录：完整代码#includestdio.h#includestdlib.h#includetime.hstructnode{floatvalue;floatweight;};floatValue,curvalue=0;floatWeight,curweight=0;//按价重比冒泡排序voidsort(nodeNode[],intM){inti,j;nodetemp;for(i=0;iM-1;i++){for(j=i+1;jM;j++){if((Node[i].value/(float)Node[i].weight)Node[j].value/(float)Node[j].weight){temp=Node[i];Node[i]=Node[j];Node[j]=temp;}}}printf(物品的价重比从高到低依次排列为：\n);for(i=0;iM;i++){printf(%.2f,Node[i].value);}printf(\n);for(i=0;iM;i++){printf(%.2f,Node[i].weight);}}//装包主要方法及输出voidpack(nodeNode[],intM){inti,j=1;printf(\n\n选中物品的价格为：\n);for(i=0;iM;i++){if((Node[i].weight+curweight)=Weight){curvalue+=Node[i].value;curweight+=Node[i].weight;printf(第j次选择为：%.2f\n,curvalue);j++;}}}intmain(){inti,M;printf(\n请输入背包容积：);scanf(%f,&Weight);printf(\n请输入物品个数：);scanf(%d,&M);nodeNode[M];srand(time==NULL);for(i=0;iM;i++){Node[i].weight=rand()%10;Node[i].value=rand()%10;}sort(Node,M);pack(Node,M);return0;}