貪心算法Dijkstra普里姆(Prim)克魯斯卡爾算法,最短路算法

實(shí)驗(yàn)（實(shí)訓(xùn)）報(bào)告遼寧科技大學(xué) 學(xué)院（系） 專(zhuān)業(yè) 時(shí)間： 課程名稱： 算法 實(shí)驗(yàn)（實(shí)訓(xùn)）題目：貪心算法的應(yīng)用班級(jí)：姓名學(xué)號(hào)機(jī)臺(tái)號(hào)任課程教師實(shí)驗(yàn)（實(shí)訓(xùn)）目的：掌握貪心算法的基本要素，包括貪心選擇性質(zhì)與最優(yōu)子結(jié)構(gòu)性質(zhì)。掌握貪心算法解決問(wèn)題的基本步驟，并利用它解決實(shí)際問(wèn)題。3?熟練掌握Dijkstra、普里姆（Prim）與克魯斯卡爾算法（Kruskal）。實(shí)驗(yàn)(實(shí)訓(xùn))原理、裝置、內(nèi)容、步驟、數(shù)據(jù)記錄及結(jié)果分析：1.已知3個(gè)物體與個(gè)背包，物體重量為W=(W],w2,w3)=(18,15,10),價(jià)值P=(p1，p2，p3)=(25,24,15),背包的容量為M=20,物品可以分割成任意大小，要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘?。答案?0,1,1/2)，最優(yōu)值為31.5。#includevstdio.h>voidSort(intn,floatv[],floatw[]){inti;floatt;for(i=1;ivn;i++)if(v[i]>v[i+1]){t=v[i];v[i]=v[i+1];v[i+1]=t;}for(i=1;i<n;i++)if(w[i]>w[i+1]){t=w[i];w[i]=w[i+1];w[i+1]=t;}}voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);for(inti=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=l;c-=w[i];}if(iv=n)x[i]=c/w[i];for(i=1;iv=n;i++)printf("%f\n",x[i]);}voidmain(){floatw[]={0,10,15,18},value=0;floatv[]={0,15,24,25};floatx[]={0,0,0,0};Knapsack(3,20,v,w,x);for(inti=1;i<4;i++)value=value+x[i]*v[i];printf("TotalValue:%f",value);}4.裝載問(wèn)題描述如下：有一批共n個(gè)集裝箱要裝上艘載重量為c的輪船，其中集裝箱i的重量為Wj。找出一種最優(yōu)裝載方案，將輪船盡可能裝滿，即在裝載體積不受限制的情況下，將盡可能重的集裝箱裝上輪船。#includevstdio.h>voidSort(inta[],intt[],intn){inttemp,min;for(inti=l;iv=n;i++) t[i]=i;for(i=1;i<=n;i++){min=i;for(intj=i+1;jv=n;j++)if(a[j]<a[min])min=j;temp=a[i];a[i]=a[min];a[min]=temp;

temp=t[i];t[i]=t[min];t[min]=temp;}voidLoading(intx[],intw[],intc,intn){int*t=newint[n+1];inti;Sort(w,t,n);for(i=1;i<=n;i++)x[i]=0;for(i=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];? ? ..voidmain()//OAmain°_EyNeOK{intw[9]={0,100,200,50,90,150,50,20,80},x[9]={0};intc=400;Loading(x,w,c,8);for(inti=1;i<=8;i++)printf("%d\t",x[i]);printf("\n");5.已知個(gè)帶權(quán)有向圖，如圖所示，其中每條邊的權(quán)是兩個(gè)頂點(diǎn)的距離，用Dijkstra算法計(jì)算從源到所有其他各項(xiàng)點(diǎn)的最短路徑長(zhǎng)度。#includeviostream>usingnamespacestd;voidDijkstra(intn,intv,intdist[],intprev[],intc[6][6]){intmaxint=65535;bool*s=newbool[n];for(inti=1;i<=n;i++){dist[i]=c[v][i];s[i]=false;if(dist[i]=maxint)prev[i]=0;elseprev[i]=v;}dist[v]=0;s[v]=true;for(i=1;i<n;i++){inttemp=maxint;intu=v;for(intj=1;j<=n;j++)訐((!s[j])&&(dist[j]<temp)){u=j;temp=dist[j];}s[u]=true;for(j=1;j<=n;j++){if((!s[j])&&(c[u][j]<maxint)){intnewdist=dist[u]+c[u][j];訐(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}}}}}voidmain(){intn=5,v=l,u=5;inti,j;intq=0;intdist[6],prev[6];int*way=newint[n+1];intc[6”6]={{0,0,0,0,0,0},{0,0,10,65535,30,100},{0,65535,0,50,65535,65535},{0,65535,65535,0,65535,10},{0,65535,65535,20,0,60},{0,65535,65535,65535,65535,0}};Dijkstra(n,v,dist,prev,c);cout<<"Xi^IA?綁P'vvvvv"->"vvuvv"^A%aAeEQ:"<<dist[u]<<endl;intw=u;while(w!=v){ q++;way[q]=prev[w];w=prev[w];}coutvv"A?御於￡。";for(j=q;j>=1;j--)cout<<way[j]<<"->";coutvvuvvendl;}6.用普里姆(Prim)算法求的最小生成樹(shù)。#includevstdio.h>//prim#definemaxint30#defineMAXCOST1000voidprim(intc[maxint][maxint],intn)〃c[i][j]IaE^,'dOjxiDjEu3EE^A^Io±B{inti,j,k,min,lowcost[maxint],closest[maxint];bools[maxint];s[l]=true;for(i=2;i<=n;i++)/*'O^￥pa1^aE%*/{lowcost[i]=c[1][i];closest[i]=1;s[i]=false;}/*OsO?魚(yú)C6入eSOD3O?^￥paxi^u^H￥pa*/for(i=1;ivn;i++){min=MAXCOST;j=1;for(k=2;kv=n;k++)if(lowcost[k]<min&&!s[k]){min=lowcost[k];j=k;}printf("(%d,%d)",closest[j],j);/*'dOj±B*/s[j]=true;/*jp^SOD*/for(k=2;kv=n;k++)if(c[j][k]vlowcost[k]&&!s[k]){lowcost[k]=c[j][k];closest[k]=j;}}}voidmain(){intn=6,i,j,mx[maxint][maxint];for(i=0;i<=n;i++)for(j=0;j<=n;j++)mx[i][j]=MAXCOST;mx[1][2]=6;mx[l][3]=l;mx[l][4]=5;mx[2][1]=6;mx[2][3]=5;mx[2][5]=3;mx[3][l]=l;mx[3][2]=5;mx[3][4]=5;mx[3][5]=6;mx[3][6]=4;mx[4][1]=5;mx[4][3]=5;mx[4][6]=2;mx[5][2]=3;mx[5][3]=6;mx[5][6]=6;mx[6][3]=4;mx[6][4]=2;mx[6][5]=6;printf("x!DjEu3EE^±B%_￡°\n");prim(mx,n);}7?用克魯斯卡爾算法(Kruska1)求最小生成樹(shù)算法#inc1udevstdio.h>〃xiDjEu3EE^kruska1Ea^>，#defineVn6//^￥paEytypedefstruct//±B%_^a11{intbegin;intend;intweight;}edge;//AU%O%0O6intGraph[Vn][Vn]={{0},{6},{1,5},{5,0,5},{0,3,6},{0,0,4,2,6}};voidEdges(edgea[],int&n);〃E0%一土BDAkvoidSort(edgea[],int);//AADo(汩衛(wèi)》?屈述b入AD&Ea「)voidKruska1(edgeE[],int);//n6ixiDjEu3EE^intFind(int1ink[],int);〃ObA-f°?OO§pf22^voidmain(){intEn=0; //±BEyedgeEs[Vn*(Vn-1)/2];〃土^%一Edges(Es,En);Sort(Es,En);Kruska1(Es,En);}voidEdges(edgea[],int&n){printf("AU%O%0O6￡°\n");for(inti=0;i<Vn;i++){for(intj=0;j<=i;j++){printf("%d\t",Graph[i][j]);if(Graph[i][j]>0){a[n].begin=j+1;a[n].end=i+1;a[n].weight=Graph[i][j];n++;}}printf("\n");}}voidSort(edgea[],intn){for(inti=0;ivn;i++)for(intj=i+l;jvn;j++)if(a[i].weight>a[j].weight){inttemp=a[i].begin;a[i].begin=a[j].begin;a[j].begin=temp;temp=a[i].end;a[i].end=a[j].end;a[j].end=temp;temp=a[i].weight;a[i].weight=a[j].weight;a[j].weight=temp;}}voidKruskal(edgeE[],intN){intn,m,link[Vn]={0};printf("\nx!DjEu3EE^:\n");for(inti=0;i<N;i+