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

《C++应用贪心算法求解背包问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。三、实验过程：#includeusingnamespacestd;structgoodinfo{floatp;//物品效益floatw;//物品重量floatX;//物品该放的数量intflag;//物品编号};//物品信息结构体voidInsertionsort(goodinfogoods[],intn)//插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序{intj,i;for(j=2;j<=n;j++){goods[0]=goods[j];i=j-1;while(goods[0]

3、.p>goods[i].p){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}}//按物品效益，重量比值做升序排列voidbag(goodinfogoods[],floatM,intn){floatcu;inti,j;for(i=1;i<=n;i++)goods[i].X=0;cu=M;//背包剩余容量for(i=1;i

4、;j<=n;j++)/*按物品编号做降序排列*/{goods[0]=goods[j];i=j-1;while(goods[0].flag

5、--------运用贪心法解背包问题---------

6、"<

7、nfo*goods;//定义一个指针while(j){cout<<"请输入物品的总数量：";cin>>n;goods=newstructgoodinfo[n+1];//cout<<"请输入背包的最大容量：";cin>>M;cout<>goods[i].w;cout<<"请输入第"<>goods[i].p;goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重

8、量比cout<torunagian"<toexit"<>j;}}四、实验结果：对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。以上算法的时间和空间复杂度为O(n*n)，其中时间复杂度基本已经不能再优化了，但空间复杂度可以优化到O(n)。