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

实验五 应用贪心算法求解背包问题学院： 计算机科学与技术 专业：计算机科学与技术学号： 班级： 姓名： 一、实验内容：背包问题指的是：有一个承重为W的背包和n个物品，它们各自的重量和价值分别是和（），假设，求这些物品中最有价值的一个子集。如果每次选择某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。二、算法思想：首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过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=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.wcu)/若不超过容量，尽量增加物品 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) goodsi+1=goodsi; i-; goodsi+1=goods0; cout最优解为:endl; for(i=1;i=n;i+) cout第i件物品要放:; coutgoodsi.Xendl; void main() cout|-运用贪心法解背包问题-|endl; int j,n; float M; goodinfo *goods;/定义一个指针 while(j) coutn; goods=new struct goodinfo n+1;/ coutM; coutendl; int i; for(i=1;i=n;i+) goodsi.flag=i; cout请输入第igoodsi.w; cout请输入第igoodsi.p;goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比 coutendl; Insertionsort(goods,n); bag(goods,M,n); coutpress to run agianendl; coutpress to exitj;四、实验结果：对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背