算法分析与设计实验报告-装载问题、图的m着色问题.doc

《算法分析与设计实验报告-装载问题、图的m着色问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告课程计算机算法设计与分析实验名称装载问题、图的m着色问题学号姓名实验日期：实验四装载问题、图的m着色问题一．实验目的（1）学习装载问题的简单算法，掌握原理，运用C++编程实现。（2）学习图的m着色问题的简单算法，掌握原理，运用C++编程实现。二．实验内容（1）设计转载问题的算法，上机编程实现。（2）设计图的m着色问题的算法，上机编程实现。三．实验代码1.装载问题的程序代码如下：#includeusingnamespacestd;templateclassLoading{friendTypeMaxLoading(Type[],Type,int

2、,int[]);private:voidBacktrack(inti);intn,*x,*bestx;Type*w,c,cw,bestw,r;};templatevoidLoading::Backtrack(inti){if(i>n){if(cw>bestw){for(intj=1;j<=n;j++)bestx[j]=x[j];bestw=cw;}return;}r-=w[i];if(cw+w[i]<=c){x[i]=1;cw+=w[i];Backtrack(i+1);cw-=w[i];}if(cw+r>bestw){x[i]=0;Backtrack(i+

3、1);}r+=w[i];}templateTypeMaxLoading(Typew[],Typec,intn,intbestx[]){LoadingX;X.x=newint[n+1];X.w=w;X.c=c;X.n=n;X.bestx=bestx;X.bestw=0;X.cw=0;X.r=0;for(inti=1;i<=n;i++)X.r+=w[i];X.Backtrack(1);delete[]X.x;cout<<"所取物品：";for(i=1;i<=n;i++)cout<

4、ntw[100],c,n,bestx[6];cout<<"输入物品个数(小于100)：";cin>>n;cout<<"输入"<>w[i];cout<<"输入第一艘轮船的载重量：";cin>>c;cout<usingnamespacestd;intsum;//判断对顶点k着色以后是否合法着色boolok(intx[],intk,boolc[5][5]

5、,intn){inti;for(i=0;i=0){x[k]++;while((x[k]<=m)&&(!ok(x,k,c,n)))//

6、得到最高标值的颜色x[k]++;if(x[k]<=m)//第k个顶点的染色是合法的{if(k==n-1)//所有的顶点都已经染完色，程序退出{sum++;printf("第中%d方案：",sum);for(i=0;i

7、0;j<5;j++)c[i][j]=true;//定义图，也可以设置成数组表示距离矩阵的形式c[0][4]=false;c[2][4]=false;c[4][0]=false;c[4][2]=false;//对5个顶点的图进行4着色m_coloring(5,4,x,c);if(sum==0)cout<<"无解"<