实验三-贪心算法

实验三贪心算法基本题一：多机调度问题一、实验目的与要求1、熟悉多机调度问题的算法；2、初步掌握贪心算法；二、实验题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。三、实验提示1、把作业按加工所用的时间从大到小排序2、如果作业数目比机器的数目少或相等，则直接把作业分配下去3、如果作业数目比机器的数目多，则每台机器上先分配一个作业，如下的作业分配时，是选那个表头上s最小的链表加入新作业。#includeiostream#includeiomanipusingnamespacestd;typedefstructJob//作业{intID;inttime;}Job;typedefstructJobNode//作业链表的节点{intID;inttime;JobNode*next;}JobNode,*pJobNode;typedefstructHeader//链表的表头{ints;//处理机上的时间；JobNode*next;}Header,pHeader;intmain(){voidQuickSort(Job*job,intleft,intright);//将job时间排序voidoutSort(Job*job,intn);//输出排序voiddisplay(Header*M,intm);//输出每个每台机器处理的工作序号数intSelectMin(Header*M,intm);//分配作业时选取机器函数；voidsolve(Header*head,Job*job,intn,intm);//作业分配函数；intm,n;cout\t\t《多机调度问题》\n;cout请输入机器台数m:;cinm;Header*head=newHeader[m];//动态构建数组结构体，用于记录机器的作业时间；cout请输入作业个数n:;cinn;Job*job=newJob[n];//动态构建作业的数组结构体；cout\n请按序号输入每个作业调度所需时间time：;for(inti=0;in;i++){cinjob[i].time;job[i].ID=i;}QuickSort(job,0,n-1);//作业排序outSort(job,n);//输出排序solve(head,job,n,m);//作业分配display(head,m);//输出分配coutendlendl;return0;}intSelectMin(Header*M,intm)//选择s最小的机器序号k;{intk=0;for(inti=1;im;i++){if(M[i].sM[k].s)k=i;//k记录S最小的序号；}returnk;}voidQuickSort(Job*job,intleft,intright)//小到大，排序{intmiddle=0,i=left,j=right;Jobitemp;middle=job[(left+right)/2].time;do{while((job[i].timemiddle)&&(iright))i++;while((job[j].timemiddle)&&(jleft))j--;if(i=j){itemp=job[j];job[j]=job[i];job[i]=itemp;i++;j--;}}while(i=j);if(leftj)QuickSort(job,left,j);if(righti)QuickSort(job,i,right);}voiddisplay(Header*M,intm)//作业分配输出函数；{JobNode*p;for(inti=0;im;i++){cout\n第i台机器上处理的工作序号：;if(M[i].next==0)continue;p=M[i].next;do{coutp-ID'';p=p-next;}while(p!=0);}}voidoutSort(Job*job,intn)//作业时间由大到小排序后输出函数；{cout\n按工作时间由大到小为:\n时间：\t;for(inti=0;in;i++)coutsetw(4)job[i].time;cout\n序号：\t;for(i=0;in;i++)coutsetw(4)job[i].ID;}voidsolve(Header*head,Job*job,intn,intm)//作业分配函数；{intk;for(inti=0;im&∈i++){JobNode*jobnode=newJobNode;jobnode-time=job[i].time;jobnode-ID=job[i].ID;jobnode-next=0;head[i].s=jobnode-time;head[i].next=jobnode;}if(i=m)//nm的情况续处理；{for(i;im;i++){head[i].s=0;head[i].next=0;}}if(nm){for(i;in;i++){JobNode*p;JobNode*jobnode=newJobNode;jobnode-time=job[i].time;jobnode-ID=job[i].ID;jobnode-next=0;k=SelectMin(head,m);p=head[k].next;head[k].s+=jobnode-time;while(p-next!=0)p=p-next;p-next=jobnode;}}}运行结果：提高题一：用贪心算法求解最小生成树一、实验要求与目的1、熟悉贪心算法的基本原理与适用范围。2、使用贪心算法编程，求解最小生成树问题。二、实验内容1、任选一种贪心算法（Prim或Kruskal），求解最小生成树。对算法进行描述和复杂性分析。编程实现，并给出测试实例#includestdio.h#includelimits.h//图中顶点个数#defineV5//未在mstSet中的点的集合中，找出最小key的点intminKey(intkey[],boolmstSet[]){intmin=INT_MAX,min_index;for(intv=0;vV;v++)if(mstSet[v]==false&&key[v]min)min=key[v],min_index=v;returnmin_index;}//打印MSTintprintMST(intparent[],intn,intgraph[V][V]){printf(EdgeWeight\n);for(inti=1;iV;i++)printf(%d-%d%d\n,parent[i],i,graph[i][parent[i]]);return0;}//Prim算法voidprimMST(intgraph[V][V]){intparent[V];//保持MST信息intkey[V];//所有顶点的代价值boolmstSet[V];//当前包含在MST中点的集合//初始为无穷大for(inti=0;iV;i++)key[i]=INT_MAX,mstSet[i]=false;key[0]=0;//parent[0]=-1;//第一个作为树的根。//MST有V的顶点for(intcount=0;countV-1;count++){intu=minKey(key,mstSet);//添加u到MSTSetmstSet[u]=true;//更新和u相连的顶点的代价for(intv=0;vV;v++)if(graph[u][v]&&mstSet[v]==false&&graph[u][v]key[v])parent[v]=u,key[v]=graph[u][v];}//打印生成的MSTprintMST(parent,V,graph);}intmain(){/*创建以下的图23(0)--(1)--(2)|/\|6|8/\5|7|/\|(3)-------(4)9*/intgraph[V][V]={{0,2,0,6,0},{2,0,3,8,5},{0,3,0,0,7},{6,8,0,0,9},{0,5,7,9,0},};//PrintthesolutionprimMST(graph);return0;}运行结果：时间复杂度这里记顶点数v，边数e时间复杂度：O(v^2).如果使用链接表存储的方式并使用堆，复杂度可以为：O(elog2v)提高题二：汽车加油问题一、实验目的与要求1、掌握汽车加油问题的算法；2、进一步掌握贪心算法；二、实验题一辆汽车加满油后可以行驶N千米。旅途中有若干个加油站。若要使沿途的加油次数最少，设计一个有效的算法，指出应在那些加油站停靠加油。并证明你的算法能产生一个最优解。三、实验提示把两加油站的距离放在数组中，a[1..n]表示从起始位置开始跑，经过n个加油站，a[k]表示第k－1个加油站到第k个加油站的距离。汽车在运行的过程中如果能跑到下一个站则不加油，否则要加油。（算法略）#includestdio.h#defineN1000intgreedy(intd[],intn,intk){intnum=0;inti=0;ints=0;for(i=0;ik;i++){if(d[i]n){printf(nosolution\n);return0;}}for(i=0,s=0;ik;i++){s+=d[i];if(sn){num++;s=d[i];}}printf(%d\n,num);return1;}voidmain(){inti,n,k;intd[N];printf(请输入汽车可行驶：\n);scanf(%d,&n);printf(加油站的个数：\n);scanf(%d,&k);for(i=0;ik+1;i++){printf(请输入第%d段路的长度:,i+1);scanf(%d,&d[i]);fflush(stdin);}greedy(d,n,k+1);}运行结果：四、实验总结本次实验让我们熟练的掌握了贪心算法的两个重要的性质：最优子结构性质和贪心选择性质。我们只有不断的练习和实验，才能更好的掌握贪心算法，知道贪心算法的优缺点，在什么情况下使用贪心算法才能更好的发挥它的作用。