贪心算法实验(求解背包问题)

算法分析与设计实验报告第四次实验姓名学号班级时间10.17上午地点工训楼309实验名称贪心算法实验(求解背包问题)实验目的通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。程序思路：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。（1）首先将单位重量的平均价值排序。（2）根据背包容量依次将平均价值高的物品放入背包中。实验步骤（1）首先计算每种物品单位重量的价值vi/wi；（2）依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包；（3）若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包；（4）依此策略一直地进行下去，直到背包装满为止。关键代码boolcomparison(sta,stb){//自定义函数说明sort函数使用的模式是从大到小排序returna.pervalb.perval;}voidKnapsack(intn,floatm,stitem[],floatx[]){inti;floattem[N];//该变量数组用来记录排好序之后的物品是否被放入背包floattmp[N];//定义一个数组用来保存以前的编号及重量，用于构造最优解for(i=0;in;i++)tmp[i]=item[i].w;sort(item,item+n,comparison);//实现单位重量的平均价值的物品的排序for(i=0;in;i++)//初始化数组x[]及tem[]{x[i]=0,tem[i]=0;};floatc=m;for(i=0;in;i++)//物品整件被装下，则x[i]=1;{if(item[i].wc)break;tem[i]=1;c-=item[i].w;}if(in)//物品只有部分被装下tem[i]=c/item[i].w;for(i=0;in;i++)//将排好序的物品编号与原始编号匹配{for(intj=0;jn;j++)//构造最优解{if(item[i].w==tmp[j])x[j]=tem[i];}}}测试结果输入较小的结果：附录：完整代码（贪心法）//贪心算法背包问题#includeiostream#includealgorithm#includetime.h#includeiomanipusingnamespacestd;constintN=10000;输入较大的结果：实验心得首先这个实验，需要注意的点是背包问题与0-1背包不同，物品可以部分的放入背包中，所以思路也不一样，首先就是将物品按照单位质量价值排序，只这一点就有一点难度。难度在于要是排序后物品的编号就会发生改变，输出的就不是之前的编号的物品，导致错误，后来发现如果为每一个物品保存一个副本，然后将它们的编号进行对比，就可以进行正确的输出了。其中这个实验让我学到了两点：一是结构体的使用，之前一直没有怎么用过，现在才发现自己其实不会用；二十对于库函数sort函数的使用。感觉每一次实验都有学到东西，很开心。实验得分助教签名structst{//定义结构体，用来存放和物品相关的变量floatv;floatw;floatperval;};voidKnapsack(intn,floatm,stitem[],floatx[]);//声明贪心算法求解问题函数intmain(){floatm;intn,i;cout请输入背包的容量：;cinm;cout请输入物品的个数：;cinn;stitem[N];floatx[N+1];cout待装物品的重量为：endl;for(i=0;in;i++)cinitem[i].w;coutendl;cout待装物品的价值为：endl;for(i=0;in;i++)cinitem[i].v;coutendl;//计算每一个物品的单位重量的价值for(i=0;in;i++)item[i].perval=item[i].v/item[i].w;clock_tstart,end,over;//计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();Knapsack(n,m,item,x);//调用贪心算法函数cout选?择?装Á¡ã下?的Ì?物?品¡¤的Ì?比À¨¨例¤y如¨?下?：êoendl;//输出最优解编号及比例for(i=0;in;i++)cout[i+1]:x[i]endl;end=clock();printf(Thetimeis%6.3f,(double)(end-start-over)/CLK_TCK);//显示运行时间system(pause);return0;}boolcomparison(sta,stb){//自定义函数说明sort函数使用的形式是从大到小排序returna.pervalb.perval;}voidKnapsack(intn,floatm,stitem[],floatx[]){inti;floattem[N];//该变量数组用来记录排好序之后的物品是否被放入背包floattmp[N];//定义一个数组用来保存以前的编号及重量，用于构造最优解for(i=0;in;i++)tmp[i]=item[i].w;sort(item,item+n,comparison);//实现单位重量的平均价值的物品的排序for(i=0;in;i++)//初始化数组x[]及tem[]{x[i]=0,tem[i]=0;};floatc=m;for(i=0;in;i++)//物品整件被装下，则x[i]=1;{if(item[i].wc)break;tem[i]=1;c-=item[i].w;}if(in)//物品只有部分被装下tem[i]=c/item[i].w;for(i=0;in;i++)//将排好序的物品编号与原始编号匹配{for(intj=0;jn;j++)//构造最优解{if(item[i].w==tmp[j])x[j]=tem[i];}}}