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

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

2、Backtrack(int i);int n, *x,*bestx;Type *w, c, cw, bestw, r;templatevoid Loading:Backtrack(int i)if(in)if(cwbestw) for(int j=1;j=n;j+) bestxj=xj;bestw=cw;return;r-=wi;if(cw+wibestw)xi=0;Backtrack(i+1);r+=wi; templateType MaxLoading(Type w,Type c,int n,int bestx) LoadingX;X.x=new intn+1;X.w=w;X.c=c;X.

3、n=n;X.bestx=bestx;X.bestw=0;X.cw=0;X.r=0;for(int i=1;i=n;i+)X.r+=wi;X.Backtrack(1);delete X.x;cout所取物品：;for(i=1;i=n;i+)coutbestxi ;return X.bestw;void main() int w100,c,n,bestx6;coutn;cout输入n个物品重量：;for(int i=1;iwi;coutc;coutendl最大装载重量为：MaxLoading(w,c,n,bestx)endl;2. 图的m着色问题的程序代码如下：#include using nam

4、espace std;int sum;/ 判断对顶点k着色以后是否合法着色bool ok(int x, int k, bool c55, int n) int i; for(i = 0; i k; i+) if(cki & xk = xi) / 第k个顶点与某个相邻的顶点有颜色冲突 return false; return true; / 合法/ 输入n为顶点个数，颜色数m，图的邻接矩阵c/ 输出n个顶点的着色xvoid m_coloring(int n, int m, int x, bool c55) int i, k; / 一开始各个顶点无颜色 for(i = 0; i = 0) xk+;

5、 while(xk = m) & (!ok(x, k, c, n) / 得到最高标值的颜色 xk+; if(xk = m) / 第k个顶点的染色是合法的 if(k = n - 1) / 所有的顶点都已经染完色，程序退出 sum+; printf(n第中%d方案：,sum); for(i=0;in;i+) printf(%d ,xi); continue; /不能用break，否则求出一个结果程序就结束了 else k+; / 继续下一个顶点的染色 else / 第k个顶点的染色不合法，回溯 xk = 0; k-; / testint main() / 初始化 bool c55;int x5; int i, j; for(i = 0; i 5; i+) for(j = 0; j 5; j+) cij = true;/ 定义图，也可以设置成数组表示距离矩阵的形式 c04 = false; c24 = false; c40 = false; c42 = false; / 对5个顶点的图进行4着色 m_coloring(5, 4