贪心算法试验求解背包问题

算法分析与设计实验报告算法分析与设计实验报告 第第 四四 次实验次实验 姓名 时间 学号 地点 班级 工训楼 30910.17 上午 实验名称贪心算法实验( (求解背包问题) ) 实验目的通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。 实验原理 给定任意几组数据， 利用贪心算法的思想， 将物品装入背包并使得其价值最大。 程序思路： 与 0-1 背包问题类似，所不同的是在选择物品i 装入背包时，可以选择物 品 i 的一部分，而不一定要全部装入背包，1≤i≤n。 （1）首先将单位重量的平均价值排序。 （2）根据背包容量依次将平均价值高的物品放入背包中。 （1）首先计算每种物品单位重量的价值vi/wi； （2）依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包； （3）若将这种物品全部装入背包后，背包内的物品总重量未超过 C，则选择 单位重量价值次高的物品并尽可能多地装入背包； （4）依此策略一直地进行下去，直到背包装满为止。 实验步骤 关键代码 bool comparison(st a,st b){//自定义函数说明sort函数使用 的模式是从大到小排序 return a.pervalb.perval; } void Knapsack(int n,float m,st item[],float x[]) { int i; float tem[N];//该变量数组用来记录排好序之后的物品是 否被放入背包 float tmp[N];//定义一个数组用来保存以前的编号及重量， 用于构造最优解 for(i=0;im; coutitem[i].w; coutitem[i].v; coutendl; //计算每一个物品的单位重量的价值 for(i=0;in;i++) item[i].perval=item[i].v/item[i].w; clock_t start,end,over;//计算程序运行时间的算法 start=clock(); end=clock(); over=end-start; start=clock(); Knapsack(n,m,item,x);//调用贪心算法函数 cout“选?择?装Á¡ã下?的Ì?物?品¡¤的Ì?比À¨¨例¤y如¨?下?： êo“endl; //输出最优解编号及比例 for(i=0;in;i++) 4 / 6 cout“[“i+1“]:“x[i]b.perval; } void Knapsack(int n,float m,st item[],float x[]) { int i; float tem[N];//该变量数组用来记录排好序之后的物品是否被放入背包 float tmp[N];//定义一个数组用来保存以前的编号及重量，用于构造最 优解 for(i=0;in;i++) tmp[i]=item[i].w; sort(item,item+n,comparison);//实现单位重量的平均价值的物品的排 序 for(i=0;in;i++)//初始化数组x[]及tem[] {x[i]=0,tem[i]=0;}; float c=m; for(i=0;ic) break; tem[i]=1; c-=item[i].w; } if(in)//物品只有部分被装下 tem[i]=c/item[i].w; for(i=0;in;i++)//将排好序的物品编号与原始编号匹配 { for(int j=0;jn;j++)//构造最优解 { if(item[i].w==tmp[j]) 5 / 6 } } } x[j]=tem[i]; 6 / 6