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

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

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

2、MaxLoading(Type[],Type,int,int[]);private:voidBacktrack(inti);intn,*x,*bcstx;Typebestw,r；}；template::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]v=c){x[i]=l；cw+=w[i];Backtrack(i+1);

3、cw-=w[i];}if(cw+r>bestw){x[i]=O;Backtrack(i+1);}r+=w[ij;)templateX;X.x=newint[n+l];X.w=w;X.c=c;X.n=n;X.bcstx=bcstx;X.bestw=O;X.cw=O;X.r=O;for(inti=l;i<=n;i++)X.r+=wfi];X.Backtrack(l);delete[]X.x;cout«n

4、所取物品：“；for(i=l;i<=n;i++)cout«bestx[i]«HM;returnX.bcstw;}voidmain(){intw[100],c，n,bestx⑹;cout«H输入物品个数(小于100)：M;cin»n;cout«n输入“vvnvv”个物詁重量：“；for(inti=1;i

5、deusingnamespacestd;intsum;//判断对顶点k看色以后是否合法看色boolok(intx[],intk,boolc[5][5],intn){inti；for(i=0;i

6、nti,k;//一开始各个顶点无颜色for(i=0;ivn;i++)x[ij=0;k=0;//从第0个顶点开始着色whilc(k>=0){x[k]++;while((x[k]<=m)&&(!ok(x,k,c,n)))//得到最高标值的颜色x[k]++;if(x[k]<=m)//第k个顶点的染色是合法的{if(k==n-l)〃所冇的顶点都已经染完色，程序退出{SU1T1++；printf(H第中％d方案:”,sum);for(i=0;i

7、一个结果程序就结束了}elsek++;〃继续下一个顶点的染色}else//第k个顶点的染色不合法，回溯{X[k]=0;k—；}}}//testintmain(){//初始化boolc[5J[5J;intx[5J;inti,j；for(i=0;i<5;i++)for(j=0;j<5;j++)cliJIjJ=true;//定义图，也可以设置成数组表示距离矩阵的形式c[0][4]=false;c[2][4]=false;c[4][0]=false;c⑷[2]=false;//对5个顶点的图进行4着色m_coloring(5,4,x,c);if

8、(sum==O)cout«H无解H«endl;return0;}四.实验结果(1)装载问题程序运行结果如下:品重量：152028324550输入6个物品重量：1520蠶入第一腹轮船的载重量：所取物品：011