算法单源最短路径、多级调度实验报告

中南大学算法设计与分析》实验报告姓名：吴冰专业班级：软件1002学号：3902100216指导教师：刘莉平完成日期：2011.11一实验名称贪心算法实验二实验目的了解贪心算法思想掌握贪心法典型问题，如背包问题、作业调度问题等。三、实验内容(1)编写一个简单的程序，实现单源最短路径问题。(2)编写一段程序，实现找零。【问题描述】当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案(要求找出的硬币数目最少)。编写程序实现多机调度问题【问题描述】要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。四、算法思想分析贪心算法：总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。贪心法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。五、算法源代码及用户屏幕(1)编写一个简单的程序，实现单源最短路径问题。#include<iostream>#include<stdlib.h>usingnamespacestd;#defineMAX1000000 〃充?当ij入"无T穷?大茁®"#defineLENsizeof(structV_sub_S)#defineN5#defineNULL0ints; 〃输°?入“?的i?源应点i?intD[N]; 〃记?录?最A?短••-路戸径？intS[N]; 〃最A?短••-距•匕离0?已。?确•[0定;§的i?顶如点1?集[¥constintG[N][N]={{0,10,MAX,30,100},{MAX,0,50,MAX,MAX},{MAX,MAX,0,MAX,10},{MAX,MAX,20,0,60},{MAX,MAX,MAX,MAX,0}};typedefstructV_sub_S //V-S链旬玄表A^a{intnum;structV_sub_S*next;};structV_sub_S*create(){structV_sub_S*head,*p1,*p2;intn=0;head=NULL;p1=(V_sub_S*)malloc(LEN);p1->num=s;head=p1;for(inti=0;i<N+1;i++){if(i!=s){++n;if(n==1)head=p1;elsep2->next=p1;p2=p1;p1=(V_sub_S*)malloc(LEN);p1->num=i;p1->next=NULL;}}free(p1);returnhead;}structV_sub_S*DelMin(V_sub_S*head,inti)//删;？除y链站玄表入中中D值丘为ai的i?结飞点i?{V_sub_S*p1,*p2;p1=head;while(i!=p1->num&&p1->next!=NULL){p2=p1;p1=p1->next;}p2->next=p1->next;returnhead;}voidDijkstra(V_sub_S*head,ints){structV_sub_S*p;intmin;S[0]=s;for(inti=0;i<N;i++){D[i]=G[s][i];}for(inti=1;i<N;i++){p=head->next;min=p->num;while(p->next!=NULL){if(D[p->num]>D[(p->next)->num])min=(p->next)->num;p=p->next;}S[i]=min;head=DelMin(head,min);p=head->next;while(p!=NULL){if(D[p->num]>D[min]+G[min][p->num]){D[p->num]=D[min]+G[min][p->num];}p=p->next;}}}voidPrint(structV_sub_S*head){structV_sub_S*p;p=head->next;while(p!=NULL){if(D[p->num]!=MAX){cout<<"D["<<p->num<<"]:"<<D[p->num]<<endl;p=p->next;}else{cout<<"D["<<p->num<<"]:"<<〃8T"vvendl;p=p->next;}}}intmain(){structV_sub_S*head;cout<<"输°?入“?源应点i?s(0至【」I?4之?间?)：";cin>>s;head=create();Dijkstra(head,s);head=create();Print(head);system("pause");return0;}(2)编写一段程序，实现找零。【问题描述】当前有面值分别为2角5分,1角，5分，1分的硬币，请给出找n分钱的最佳方案(要求找出的硬币数目最少)。〃输入：数组m,依次存放从大到小排列的面值数，n为需要找的钱数，单位全部为分//输出：找钱方案#include<iostream>usingnamespacestd;#defineNUM4voidmain(){intm[NUM]={25,10,5,1};intmeishu[NUM]={0,0,0,0};intn;//假设n=99coutvv"请输入付款金额(分)：";cin>>n;coutvvnvv"分的找钱方案为："vvendl;for(inti=0;i<NUM;i++){while(n>=m[i]&&n>0)meishu[i]++;//cout<<m[i]<<""n-=m[i];}coutvvm[i]vv"分需要"vvmeishu[i]vv"个"<<""vvendl;}}(3)编写程序实现多机调度问题【问题描述】要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理但未完工前不允许中断处理。作业不能拆分成更小的子作业。#includeviostream>usingnamespacestd;#defineN10#defineM3voidsort(intt[],intn);intset_work1(intt[],intn);intmax(intt[],intnum);intmin(intt[],intm);intset_work2(intt[],intn);staticinttime[N]={2,8,18,32,50,72,98,128,182,200},s[M]={0,0,0};voidmain(){sort(time,N);if(M>=N) //作业数小于机器数{coutvv"最短时间为"vvset_workl(time,N)vvendl;}else{coutvv"最短时间为"vvset_work2(time,N)vvendl;}system("PAUSE");}voidsort(intt[],intn){for(intk=0;kvn-l;k++) //用选择法将处理时间从大到小排序{intj=k;for(inti=k;ivn;i++){if(t[i]>t[j]){j=i;}}{inttemp=t[j];t[j]=t[k];t[k]=temp;}intmax(intt[],intnum)//max函数求解处理时间总和最长{intmax=t[0];for(inti=1;i<num;i++){if(max<t[i])max=t[i];}returnmax;}intmin(intt[],intm){intmin=0; //min记录目前处理作业时间和最小的机器号for(inti=1;i<m;i++){if(s[min]>s[i])min=i;}returnmin;}intset_work1(intt[],intn){intm=0;for(inti=0;i<n;i++)//分派作业{s[m++]+=t[i];}returnmax(s,N);intset_work2(intt[],intn){for(inti=0;i<n;i++){s[min(s,M)]+=t[i];}returnmax(s,M);}六、实验过程分析对最短路径中红点集蓝点集的