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

《贪心算法实验(求解背包问题).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、vi/wi；（2）依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包；（3）若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包；（4）依此策略一直地进行下去，直到背包装满为止。关键代码boolcomparison(sta,stb){//自定义函数说明sort函数使用的模式是从大到小排序returna.perval>b.perval;}voidKnapsack(intn,floatm,stitem[],floatx[]){inti;floattem[N];//

3、该变量数组用来记录排好序之后的物品是否被放入背包floattmp[N];//定义一个数组用来保存以前的编号及重量，用于构造最优解for(i=0;ic)break;t

4、em[i]=1;c-=item[i].w;}if(i

5、于要是排序后物品的编号就会发生改变，输出的就不是之前的编号的物品，导致错误，后来发现如果为每一个物品保存一个副本，然后将它们的编号进行对比，就可以进行正确的输出了。其中这个实验让我学到了两点：一是结构体的使用，之前一直没有怎么用过，现在才发现自己其实不会用；二十对于库函数sort函数的使用。感觉每一次实验都有学到东西，很开心。实验得分助教签名附录：完整代码（贪心法）//贪心算法背包问题#include#include#include#include

6、p>usingnamespacestd;constintN=10000;structst{//定义结构体，用来存放和物品相关的变量floatv;floatw;floatperval;};voidKnapsack(intn,floatm,stitem[],floatx[]);//声明贪心算法求解问题函数intmain(){floatm;intn,i;cout<<"请输入背包的容量：";cin>>m;cout<<"请输入物品的个数：";cin>>n;stitem[N];floatx[N+1];cout<<"待装物品的重量为

7、："<>item[i].w;cout<>item[i].v;cout<

8、tart=clock();Knapsack(n,m,item,x);//调用贪心算法函数cout<<"选?择?装Á¡ã下?的Ì?物?品¡¤的Ì?比À¨¨例¤y如¨?下?：êo"<