C++应用贪心算法求解背包问题

1、实验五应用贪心算法求解背包问题学院：计算机科学与技术专业：计算机科学与技术学号：班级：姓名：一、实验内容：背包问题指的是：有一个承重为W的背包和n个物品，它们各自的重量和价值分别是w和v(1in)，假设W，工w，求这些物品中最有价值的一个子集。如果每次选择iiii=1某一个物品的时候，只能全部拿走，则这一问题称为离散(0-1)背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。二、算法思想：首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值

2、次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。三、实验过程：#includeusingnamespacestd;structgoodinfofloatp;/物品效益floatw;/物品重量floatX;/物品该放的数量intflag;/物品编号;/物品信息结构体voidInsertionsort(goodinfogoods,intn)插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序intj,i;for(j=2;jgoodsi.p)goodsi+1=goodsi;i-;goodsi+1=goods0;/按物品效益，重量比值做升序排列voidbag(good

3、infogoods,floatM,intn)floatcu;inti,j;for(i=1;i=n;i+)goodsi.X=0;cu=M;/背包剩余容量for(i=1;in;i+)if(goodsi.wvcu)若不超过容量，尽量增加物品goodsi.X=1;cu-=goodsi.w;确定背包新的剩余容量elsegoodsi.X=0;for(j=2;j=n;j+)/*按物品编号做降序排列*/goods0=goodsj;i=j-1;while(goods0.flaggoodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;coutvv最优解为:vvendl;for

4、(i=1;in;goods=newstructgoodinfon+1；/coutvv请输入背包的最大容量：；cinM；coutvvendl；inti；for(i=1；iv=n；i+)goodsi.flag=i；coutvv请输入第vvivv件物品的重量:；cingoodsi.w；coutvv请输入第vvivv件物品的效益:；cingoodsi.p；goodsi.p=goodsi.p/goodsi.w;得出物品的效益，重量比coutvvendl；Insertionsort(goods,n)；bag(goods,M,n)；coutvvpressv1torunagianvvendl；coutvvpressv0toexitvvendl；cinj；四、实验结果：对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公