算法分析與設(shè)計(jì)實(shí)驗(yàn)報告-裝載問題、圖的m著色問題

1、實(shí)驗(yàn)報告課程計(jì)算機(jī)算法設(shè)計(jì)與分析實(shí)驗(yàn)名稱裝載問題、圖的m著色問題學(xué)號姓名實(shí)驗(yàn)日期：實(shí)驗(yàn)四 裝載問題、圖的m著色問題一實(shí)驗(yàn)?zāi)康模?） 學(xué)習(xí)裝載問題的簡單算法，掌握原理，運(yùn)用C+編程實(shí)現(xiàn)。（2） 學(xué)習(xí)圖的m著色問題的簡單算法，掌握原理，運(yùn)用C+編程實(shí)現(xiàn)。二實(shí)驗(yàn)內(nèi)容（1）設(shè)計(jì)轉(zhuǎn)載問題的算法，上機(jī)編程實(shí)現(xiàn)。（2）設(shè)計(jì)圖的m著色問題的算法，上機(jī)編程實(shí)現(xiàn)。三實(shí)驗(yàn)代碼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;/ 判斷對頂點(diǎn)k著色以后是否合法著色bool ok(int x, int k, bool c55, int n) int i; for(i = 0; i k; i+) if(cki & xk = xi) / 第k個頂點(diǎn)與某個相鄰的頂點(diǎn)有顏色沖突 return false; return true; / 合法/ 輸入n為頂點(diǎn)個數(shù)，顏色數(shù)m，圖的鄰接矩陣c/ 輸出n個頂點(diǎn)的著色xvoid m_coloring(int n, int m, int x, bool c55) int i, k; / 一開始各個頂點(diǎn)無顏色 for(i = 0; i = 0) xk+;

5、 while(xk = m) & (!ok(x, k, c, n) / 得到最高標(biāo)值的顏色 xk+; if(xk = m) / 第k個頂點(diǎn)的染色是合法的 if(k = n - 1) / 所有的頂點(diǎn)都已經(jīng)染完色，程序退出 sum+; printf(n第中%d方案：,sum); for(i=0;in;i+) printf(%d ,xi); continue; /不能用break，否則求出一個結(jié)果程序就結(jié)束了 else k+; / 繼續(xù)下一個頂點(diǎn)的染色 else / 第k個頂點(diǎn)的染色不合法，回溯 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;/ 定義圖，也可以設(shè)置成數(shù)組表示距離矩陣的形式 c04 = false; c24 = false; c40 = false; c42 = false; / 對5個頂點(diǎn)的圖進(jìn)行4著色 m_coloring(5, 4