《算法设计与分析》实验四_实验报告电子版

《《算法设计与分析》实验四_实验报告电子版》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、学号09710118£#A帀恵段诊淀《算法设计与分析》实验报告四学生姓名范振山专业、班级09计算机一班指导教师唐国峰成绩电子与信息工程系2012年4月6日实验四:贪心算法运用练习一、实验目的本次实验是针对贪心算法的设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。二、实验步骤与要求1•实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2.学生独自完成实验指定内容；3.实验结朿后，用统一的实验报告模板编写实验报告。4.提交说明：（1）电子版提交说明：a需耍提交Winrar压缩包，文件名为“《算法设计与

2、分析》实验四—学号一姓名”，如“《算法设计与分析》实验四_09290101_张三”。b压缩包内为一个“《算法设计与分析》实验四_学号-姓名”命名的顶层文件夹,其下为两个文件夹，一个文件夹命名为''源程序”，另一个文件夹命名为“实验报告电子版”。其下分别放置对应实验成果物。（2）打印版提交说明：a不可随意更改模板样式。b字体：中文为宋体，大小为10号字，英文为TimeNewRoman,大小为10号字。c行间距：单倍行距。（3）提交截止时间：2012年4月20日16:00。三、实验项目请从下列题日列表中任选2道或3道题日，运用贪心算法对问题的进行

3、求解。备选题目列表如下：1.教材第106页所记述的0・1背包问题。2.教材课后习题4-9；3.教材课后习题4-2K四、实验过程（一）题目一：给定n种物品和一个背包，物品i的重量是wi,其价值为vi,背包的容量为c。问如何选择装入背包中的物品，使得装入背包中物品的总价值最大？1.题目分析给定c>0;wi〉0;vo>0,lWiWn,要求找出一个n元0-1向量（xl,x2,xn）,xiG{0,1},1WiWn,使得刀wixiWe,而一FL^vixi达到最大。1.算法构造首先计算每种物品单位重量的价ffivi.wi；然后，依贪心算法策略，将尽可能多的

4、单位重量价值最高的物品装入背包。若将这种物品全装入背包后，背包内的物品总重量为超过c,则选择单位质量价值次高的物品并尽可能多地装入背包。2.算法实现//tanxin.cpp:定义控制台应用程序的入口点。//#include"stdafx.h"#includeusingnamespacestd;〃使用冒泡排序对v[]/w[]单位价值的物品进行从大到小的排序voidSort(intn,floatv[],floatw[]){floattl,t2;for(inti=0;i

5、{floata=vlij/wlij;〃比较变量floatb=v[i+1

6、/w

7、i+1]；讦(a

8、量for(i=0;ic)break;〃质量大于容量的不予考虑x[i]=l；c-=w[i];〃物品放入，剩余容量减少}if(i<=n)〃输出放入的情况x

9、

10、表示物品放入的单位质量或单位价值voidPrint(intn,floatv[],floatw[],floatx[]){inti;fo「(i=0;ivn;i++){if(x[i]!=0)n«(x

11、i]*v

12、i])«endl;coutvv“第“vvi+lvv“物品放入质量为:”《(x[i]*w[i])VV“价值是:intmain(){intn;floatM=50.

13、0;cout«H物品的种类M«endl;cin»n;cout«H背包的容量为：“vvMvvendl;〃定义动态数组float*v=newfloat

14、n

15、;float*w=newfloatfnl;float*x=newfloat[n];cout«"输入物品的价值:u«endl;for(inti=0;i

16、rn0;1.运行结果d:iS?W