贪心算法 实验二报告

实验二贪心选择算法姓名：田圆圆学号：2013125135一、实验目的与要求：理解贪心选择算法的思想。二、预习与准备：贪心选择算法思想：（1）贪心选择能得到问题的最优解，要证明我们所做的第一步选择一定包含在一个最优解总，即存在一个最优解的第一步是从我们的贪心选择开始。（2）在做出第一步贪心选择后剩下的子问题应该是和原问题类似的规模较小的子问题为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。三、实验题目：1.在无向图G=(V,E)中，假设每条边E[i]的长度为w[i]，找到由顶点V0到其余各点的最短路径。2.背包问题给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?3.多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。四、实验过程：1.用贪心算法求单元最短路径问题：其中，dist[i]：表示当前从源到顶点i的最短特殊路径长度。实验代码为：#includeiostream#includestdio.h#includelimits.husingnamespacestd;constintV=9;//定义顶点个数//从未包含在SPT的集合T中，选取一个到S集合的最短距离的顶点。intgetMinIndex(intdist[V],boolsptSet[V]){intmin=INT_MAX,min_index;for(intv=0;vV;v++)if(sptSet[v]==false&&dist[v]min)min=dist[v],min_index=v;returnmin_index;}//打印结果voidprintSolution(intdist[],intn){printf(VertexDistancefromSource\n);for(inti=0;iV;i++)printf(%d\t\t%d\n,i,dist[i]);}//source代表源点voiddijkstra(intgraph[V][V],intsource){intdist[V];//存储结果，从源点到i的距离boolsptSet[V];//sptSet[i]=true如果顶点i包含在SPT中//初始化.0代表不可达for(inti=0;iV;i++){dist[i]=(graph[source][i]==0?INT_MAX:graph[source][i]);sptSet[i]=false;}//源点，距离总是为0.并加入SPTdist[source]=0;sptSet[source]=true;//迭代V-1次，因此不用计算源点了，还剩下V-1个需要计算的顶点。for(intcount=0;countV-1;count++){//u，是T集合中，到S集合距离最小的点intu=getMinIndex(dist,sptSet);//加入SPT中sptSet[u]=true;//更新到V的距离。可以理解为Bellman-Ford中的松弛操作for(intv=0;vV;v++)if(!sptSet[v]&&graph[u][v]&&dist[u]!=INT_MAX&&dist[u]+graph[u][v]dist[v])dist[v]=dist[u]+graph[u][v];}printSolution(dist,V);}intmain(){/*以例子中的图为例*/intgraph[V][V]={{0,4,0,0,0,0,0,8,0},{4,0,8,0,0,0,0,11,0},{0,8,0,7,0,4,0,0,2},{0,0,7,0,9,14,0,0,0},{0,0,0,9,0,10,0,0,0},{0,0,4,0,10,0,2,0,0},{0,0,0,14,0,2,0,1,6},{8,11,0,0,0,0,1,0,7},{0,0,2,0,0,0,6,7,0}};dijkstra(graph,0);return0;}2.背包问题：#includestdio.hintf[10][100];//构造最优矩阵voidpackage0_1(int*w,int*v,intn,intc){inti,j;//初始化矩阵for(i=1;i=n;i++)f[i][0]=0;for(j=1;j=c;j++)f[0][j]=0;for(i=1;i=n;i++){for(j=1;j=c;j++){//当容量够放入第i个物品，并且放入之后的价值要比不放大if(w[i]=j&&f[i-1][j-w[i]]+v[i]f[i-1][j]){f[i][j]=f[i-1][j-w[i]]+v[i];}elsef[i][j]=f[i-1][j];}}printf(最大价值:%d\n,f[n][c]);}//构造最优解voidgetResult(intn,intc,int*res,int*v,int*w){inti,j;j=c;for(i=n;i=1;i--){if(f[i][j]!=f[i-1][j]){res[i]=1;j=j-w[i];}}}voidmain(){intw[6]={0,2,2,6,5,4};//每个物品的重量intv[6]={0,6,3,5,4,6};//每个物品的价值intres[5]={0,0,0,0,0};intn=5;//物品的个数intc=10;//背包能容的重量inti,j;package0_1(w,v,n,c);for(i=0;i=n;i++){for(j=0;j=c;j++)printf(%2d,f[i][j]);printf(\n);}getResult(n,c,res,v,w);printf(放入背包的物品为:\n);for(i=1;i=n;i++)if(res[i]==1)printf(%d,i);}3.多机器调配问题：#includestdafx.h#includeMinHeap.h#includeiostream#includefstreamusingnamespacestd;constintN=7;//作业个数constintM=3;//机器台数ifstreamfin(4d7.txt);classJobNode{//friendvoidGreedy(JobNode[],int,int);//friendintmain(void);public:operatorint()const{returntime;}//private:intID,time;};classMachineNode{//friendvoidGreedy(JobNode[],int,int);public:operatorint()const{returnavail;}//private:intID,avail;};templateclassTypevoidGreedy(Typea[],intn,intm);templateclassTypevoidSelectSort(Typea[],intn);intmain(){JobNodea[N+1];//各作业所需要的处理时间cout各作业所需要的处理时间为：endl;for(inti=1;i=N;i++){fina[i].IDa[i].time;coutID:a[i].ID,time:a[i].timeendl;}Greedy(a,N,M);return0;}templateclassTypevoidGreedy(Typea[],intn,intm){if(n=m)//机器数量比作业数量多，直接分配{cout直接为每个作业分配一台机器.endl;return;}SelectSort(a,n);//排序，从大到小MinHeapMachineNodeH(m);MachineNodex;for(inti=1;i=m;i++){x.avail=0;x.ID=i;H.Insert(x);}for(inti=1;i=n;i++){x=H.RemoveMin();cout将机器x.ID从x.avail到(x.avail+a[i].time)的时间段分配给作业a[i].IDendl;x.avail+=a[i].time;H.Insert(x);//根据新的avail值将x插入Heap中适当位置}}templateclassTypevoidSelectSort(Typea[],intn){Typetemp;intmax;for(inti=1;in;i++){max=i;for(intj=i+1;j=n;j++){if(a[max]a[j]){max=j;}}if(max!=i){temp=a[i];a[i]=a[max];a[max]=temp;}}}//4d7贪心算法多机调度问题#includestdafx.h#includeMinHeap.h#includeiostream#includefstreamusingnamespacestd;constintN=7;//作业个数constintM=3;//机器台数ifstreamfin(4d7.txt);classJobNode{//friendvoidGreedy(JobNode[],int,int);//friendintmain(void);public:operatorint()const{returntime;}//private:intID,time;};classMachineNode{//friendvoidGreedy(JobNode[],int,int);public:operatorint()const{returnavail;}//private:intID,avail;};templateclassTypevoidGreedy(Typea[],intn,intm);templateclassTypevoidSelectSort(Typea[],intn);intmain(){JobNodea[N+1];//各作业所需要的处理时间cout各作业所需要的处理时间为：endl;for(inti=1;i=N;i++){fina[i].IDa[i].time;coutID:a[i].ID,time:a[i].timeendl;}Greedy(a,N,M);return0;}templateclassTypevoidGreedy(Typea[],intn,intm){if(n=m)//机器数量比作业数量多，直接分配{cout直接为每个作业分配一台机器.endl;return;}SelectSort(a,n);//排序，从大到小MinHeapMachineNodeH(m);MachineNodex;for(inti=1;i=m;i++){x.avail=0;x.ID=i;H.Insert(x);}for(inti=1;i=n;i++){x=H.RemoveMin();cout将机器x.ID从x.avail到(x.avail+a[i].time)的时间段分配给作业a[i].IDendl;x.avail+=a[i].time;H.Insert(x);//根据新的avail值将x插入Heap中适当位置}}templateclassTypevoidSelectSort(Typea[],intn){Typetemp;intmax;for(inti=1;in;i++){max=i;for(intj=i+1;j=n;j++){if(a[max]a[j]){max=j;}}if(max!