贪心算法实验（求解背包问题）

1、贪心算法实验（求解背包问题） 算法分析与设计实验报告 第 四 次实验 姓名 时间 学号 地点 班级 工训楼309 10.17上午 实验名称 贪心算法实验(求解背包问题) 实验目的 通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。 实验原理 给定任意几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。 程序思路： 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。 （1） 首先将单位重量的平均价值排序。 （2） 根据背包容量依次将平均价值高的物品放入背包中。 （1）首先计算每种物品单位重量的价值vi/wi；

2、 （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 temn; /该变量数组用来记录排好序之后的物品是否被放入背包 floa

3、t tmpn; /定义一个数组用来保存以前的编号及重量，用于构造最优解 for(i=0;ic) break; temi=1; c-=itemi.w; if(i附录： 完整代码（贪心法） /贪心算法 背包问题 #include #include #include #include using namespace std; const int n=10000; struct st /定义结构体，用来存放和物品相关的变量 float v; float w; float perval; ; void knapsack(int n,float m,st item,float x); /声明贪心算法求解问

4、题函数 int main() float m; int n,i; coutm; coutn; st itemn; float xn+1; coutitemi.w; cout coutitemi.v; cout /计算每一个物品的单位重量的价值 for(i=0;i knapsack(n,m,item,x); /调用贪心算法函数 cout end=clock(); printf(,(double)(end-start-over)/clk_tck); /显示运行时间 system(); return 0; bool comparison(st a,st b)/自定义函数说明sort函数使用的形式是从大到小排序 return a.pervalb.perval; void knapsack(int n,float m,st item,float x) int i; float temn; /该变量数组用来记录排好序之后的物品是否被放入背包 float tmpn; /定义一个数组用来保存以前的编号及重量，用于构造最优解 for(i=0;i sort(item,item+n,comparison); /实现单位重量的平均价值的物品的排序