精选优质文档-倾情为你奉上算法分析与设计实验报告第 四 次实验姓名学号班级时间10.17上午地点工训楼309 实验名称贪心算法实验(求解背包问题)实验目的通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。程序思路：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。（1） 首先将单位重量的平均价值排序。（2） 根据背包容量依次将平均价值高的物品放入背包中。实验步骤（1）首先计算每种物品单位重量的价值vi/wi；（2）依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包；（3）若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包；（4）依此策略一直地进行下去，直到背包装满为止。关键代码bool comparison(st a,st b)
