算法分析实验报告--贪心算法.doc

《算法分析实验报告--贪心算法.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法设计与分析》实验报告贪心算法姓名：XXX专业班级：XXX学号：3XXX指导教师：XXX完成日期：XXX一、试验名称：贪心算法（1）写出源程序，并编译运行（2）详细记录程序调试及运行结果二、实验目的(1)了解贪心算法思想(2)掌握贪心法典型问题，如背包问题、作业调度问题等。三、实验内容(1)编写一个简单的程序，实现单源最短路径问题。(2)编写一段程序，实现找零。(3)编写程序实现多机调度问题四、算法思想分析(1)编写一个简单的程序，实现单源最短路径问题。用P，T分别表示某个点的P标号、T标号，si

2、表示第i步时，具P标号点的集合。为了在求出从vs到各点的距离的同时，也求出从Vs到各点的最短路，给每个点v以一个λ值，算法终止时λ(v)=m，表示在Vs到v的最短路上，v的前一个点是Vm；如果λ(v)=∞，表示图G中不含从Vs到v的路；λ(Vs)=0。(2)编写一段程序，实现找零。先举个例子，假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1

3、分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。(3)编写程序实现多机调度问题1、把作业按加工所用的时间从大到小排序2、如果作业数目比机器的数目少或相等，则直接把作业分配下去3、如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。五、算法源代码及用户屏幕(1)编写一个简单的程序，实现单源最短路径问题。//Dijkstra算法#include#include

4、>usingnamespacestd;#defineVEX5//定义结点的个数#definemaxpoint100doublegraph[][maxpoint]={{0,10,-1,30,100},{-1,0,50,-1,-1},{-1,-1,0,-1,10},{-1,-1,20,0,60},{-1,-1,-1,-1,0}};//邻接矩阵voidmain(){intR[maxpoint]={0},B[maxpoint];intD[VEX],P[VEX];//定义数组D用来存放结点特殊距离，P数组存放父

5、亲结点//初始时，红点集中仅有源结点0R[0]=1;B[0]=0;for(inti=1;i

6、

7、<"";//将具有最短特殊路长度的结点min添加到红点集中R[min]=1;B[min]=0;//对数组D作必要的修改for(j=1;jD[min]+graph[min][j]

8、

9、D[j]==-1){D[j]=D[min]+graph[min][j];//每次迭代求最小值，最后一次即为到源点的最短路径P[j]=min;}//输出最短路径for(i=0;i

10、i]<<"";cout<<"";for(i=0;i#defineMax25#defineMid10#defineNext5#defineMin1usingnamespacestd;inti=0;intj=0;intk=0;ints=0;inta,b,c;voidchangeMoney(intm){if(m>=Max)