《C++应用贪心算法求解背包问题》由会员分享，可在线阅读，更多相关《C++应用贪心算法求解背包问题（4页珍藏版）》请在金锄头文库上搜索。
1、实验五 应用贪心算法求解背包问题学院： 计算机科学与技术 专业：计算机科学与技术学号： 班级： 姓名：一、实验内容：背包问题指的是：有一个承重为W的背包和n个物品，它们各自的重量和价值分别是 w和v (1 in)，假设Ww，求这些物品中最有价值的一个子集。如果每次选择i iii=1 某一个物品的时候，只能全部拿走，则这一问题称为离散(0-1)背包问题；如果每次 可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。二、算法思想：首先计算每种物品单位重量的价值Vi/Wi,然后，依贪心选择策略，将尽可能多的单位 重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过
2、C,则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直 到背包装满为止。三、实验过程： #include using namespace std;struct goodinfofloat p; /物品效益float w; /物品重量 float X; /物品该放的数量 int flag; /物品编号 ;/物品信息结构体void Insertionsort(goodinfo goods,int n)/插入排序，按 pi/wi 价值收益进行排序，一般教材上 按冒泡排序int j,i;for(j=2;jgoodsi.p)goodsi+1=goodsi;i-;goodsi+1
3、=goods0;/按物品效益，重量比值做升序排列void bag(goodinfo goods,float M,int n)float cu; int i,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;确定背包新的剩余容量else goodsi.X=0;for(j=2;j=n;j+) /*按物品编号做降序排列*/ goods0=goodsj; i=j-1;while (goods0.flaggoodsi.flag)goods
4、i+1=goodsi;i-; goodsi+1=goods0; coutvv最优解为:vvendl;for(i=1;in;goods=new struct goodinfo n+1；/ coutvv请输入背包的最大容量：;cinM；coutvvendl;int i; 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);coutvvpress v1 to run agianvvendl; coutvvpress v0 to exitvvendl;cinj;四、实验结果：对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终 能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。以上算法的时间和空间复杂度为O(n*n),其中时间复杂度基本已经不能再优化了，但空间 复杂度可以优化到O(n)。
