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

实验五 应用贪心算法求解背包问题 学院： 计算机科学与技术 专业：计算机科学与技术 学号： 班级： 姓名： 一、实验内容： 背包问题指的是：有一个承重为W的背包和n个物品，它们各自的重量和价值分别是和（），假设，求这些物品中最有价值的一个子集。如果每次选择 某一个物品的时候，只能全部拿走，则这一问题称为离散（0-1）背包问题；如果每次 可以拿走某一物品的任意一部分，则这一问题称为连续背包问题。 二、算法思想： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 三、实验过程： #include iostream using namespace std; struct goodinfo { float p; //物品效益 float w; //物品重量 float X; //物品该放的数量 int flag; //物品编号 };//物品信息结构体 void Insertionsort(goodinfo goods[],int n)//插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序 { int j,i; for(j=2;j=n;j++) { goods[0]=goods[j]; i=j-1; while (goods[0].pgoods[i].p) { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; } }//按物品效益，重量比值做升序排列 void bag(goodinfo goods[],float M,int n) { float cu; int i,j; for(i=1;i=n;i++) goods[i].X=0; cu=M; //背包剩余容量 for(i=1;in;i++) { if(goods[i].wcu)//若不超过容量，尽量增加物品 { goods[i].X=1; cu-=goods[i].w;//确定背包新的剩余容量 } else { goods[i].X=0; } for(j=2;j=n;j++) /*按物品编号做降序排列*/ { goods[0]=goods[j]; i=j-1; while (goods[0].flaggoods[i].flag) { goods[i+1]=goods[i]; i--; } goods[i+1]=goods[0]; } } cout最优解为:endl; for(i=1;i=n;i++) { cout第i件物品要放:; coutgoods[i].Xendl; } } void main() { cout|--------运用贪心法解背包问题---------|endl; int j,n; float M; goodinfo *goods;//定义一个指针 while(j) { cout请输入物品的总数量：; cinn; goods=new struct goodinfo [n+1];// cout请输入背包的最大容量：; cinM; coutendl; int i; for(i=1;i=n;i++) { goods[i].flag=i; cout请输入第i件物品的重量:; cingoods[i].w; cout请输入第i件物品的效益:; cingoods[i].p; goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比