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

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