贪心算法实验(求解背包问题)

1、算法分析与设计实验报告第四次实验姓名学号班级时间10.17上午地点工训楼309实验名称贪心算法实验（求解背包问题）实验目的通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。 程序思路：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1ib.perval;void Knapsack（int n, float m,st item, float x）（int i;float temN;/该变量数组用来记录排好序之后的物品是否被放入背包float tmp

2、N;定义一个数组用来保存以前的编号及重量，用于构造最优解for （i=0;in;i+）tmpi=itemi.w;sort(item,item+n,comparison); /实现单位重量的平均价值 的物品的排序for (i=0;in;i+) xi=0,temi=0;for (i=0;in;i+) xi=0,temi=0;初始化数组x及temfloat c=m;for (i=0;in;i+)(float c=m;for (i=0;ic) break;temi=1;c-=itemi.w;if(in)物品整件被装下， Qxi=1;/物品只有部分被装下temi=c/itemi.w;for(i=0;in

3、;i+)将排好序的物品编号与原始编号匹配(for(int j=0;jn;j+) 构造最优解(if(itemi.w=tmpj)xj=temi;输入较小的结果:容个量容个量口 SE非霸品部云入物同精装物品的价值为：测试结果60 120 100测试结果上择装下的物品的比例如下：13:123 = 133=0.66667The tine is 0.019请按任意键继续.输入较大的结果:R联J笨R联J笨S3曜麒r c倾叩血亦Eg r柱瞬23 2 34 饨 44肝 21135 m 3333 6明挪245 22 46 25 6? 568 44 W 55555 34届曲糖跚遍为:34 46 卅43 111 刑朋

4、 33315 77735 11144 5?制34 m 234 885 336 7?9 345 22547 86 444选择装下的物品的比例如下:：1：1：1：1：1：1 ?：1：1：1：1：1：1：1：1：1 It ：1 1?：1 18：1 1?：0.939231 20：1The time is：区-国64i青按任清实验心得实验得分首先这个实验，需要注意的点是背包问题与0-1背包不同，物品可以部分的放 入背包中，所以思路也不一样，首先就是将物品按照单位质量价值排序，只这 一点就有一点难度。难度在于要是排序后物品的编号就会发生改变，输出的就 不是之前的编号的物品，导致错误，后来发现如果为每一个物

5、品保存一个副本， 然后将它们的编号进行对比，就可以进行正确的输出了。其中这个实验让我学 到了两点：一是结构体的使用，之前一直没有怎么用过，现在才发现自己其实 不会用；二十对于库函数sort函数的使用。感觉每一次实验都有学到东西， 很开心。实验心得实验得分助教签名附录：完整代码（贪心法）/贪心算法背包问题#include#include#include#includeusing namespace std;const int N=10000;struct st/定义结构体，用来存放和物品相关的变量float v;float w;float perval;；void Knapsack(int n,

6、 float m,st item, float x);/声明贪心算法求解问题函数int main()(float m;int n,i;coutm;coutn;st itemN;float xN+1;cout待装物品的重量为：endl;for(i=0;iitemi.w;coutendl;cout待装物品的价值为：endl;for(i=0;iitemi.v;coutendl;/计算每一个物品的单位重量的价值for(i=0;in;i+)itemi.perval=itemi.v/itemi.w;clock_t start,end,over;/计算程序运行时间的算法start=clock();end=c

7、lock();over二end-start;start=clock();Knapsack(n,m,item,x);/调用贪心算法函数cout选?择?装AjaT?的1?物？品i。的1?比A“例。y如.？下？：eoendl; /输出最优解编号及比例for(i=0;in;i+)couti+1:xib.perval;void Knapsack(int(int i;void Knapsack(int(int i;float temN;float tmpN;优解该变量数组用来记录排好序之后的物品是否被放入背包 /定义一个数组用来保存以前的编号及重量，用于构造最for(i=0;in;i+)tmpi=itemi.w;sort(item,item+n,comparison); /实现单位重量的平均价值的物品的排 序for(i=0;in;i+)for(i=0;ic)break;temi = 1;c-=itemi.w;/物品