【正文】 n amp。 } else { //回溯 x[k]=0。問題是：在 8 8的棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上。 四皇后問題的解空間樹是一個完全 4叉樹，樹的根結(jié)點表示搜索的初始狀態(tài)，從根結(jié)點到第 2層結(jié)點對應皇后 1在棋盤中第 1行的可能擺放位置，從第 2層結(jié)點到第 3層結(jié)點對應皇后 2在棋盤中第 2行的可能擺放位置，依此類推。 k=1。 !Place(k)) x[k]=x[k]+1。 i=n。amp。 } } } bool Place(int k) //考察皇后 k放置在 x[k]列是否發(fā)生沖突 { for (i=1。 } 算法設(shè)計與分析 清華大學出版社 批處理作業(yè)調(diào)度問題 n個作業(yè) {1, 2, … , n}要在兩臺機器上處理 ， 每個作業(yè)必須先由機器 1處理 ， 然后再由機器 2處理 ，機器 1處理作業(yè) i所需時間為 ai， 機器 2處理作業(yè) i所需時間為 bi（ 1≤ i≤ n） ， 批處理作業(yè)調(diào)度問題要求確定這 n個作業(yè)的最優(yōu)處理順序 ， 使得從第 1個作業(yè)在機器 1上處理開始 ， 到最后一個作業(yè)在機器 2上處理結(jié)束所需時間最少 。 作業(yè) 1:2 作業(yè) 2:3 作業(yè) 3:2 空閑 :2 作業(yè) 1:1 機器 1 機器 2 作業(yè) 2:1 作業(yè) 3:3 (a) 調(diào)度方案 (1, 2, 3)， 最后完成時間為 10 作業(yè) 1:2 作業(yè) 2:3 作業(yè) 3:2 空閑 :2 作業(yè) 1:1 機器 1 機器 2 作業(yè) 2:1 作業(yè) 3:3 (b) 調(diào)度方案 (1, 3, 2)， 最后完成時間為 8 算法設(shè)計與分析 清華大學出版社 作業(yè) 2:3 作業(yè) 1:2 作業(yè) 3:2 空閑 作業(yè) 2:1 機器 1 機器 2 作業(yè) 1:1 作業(yè) 3:3 (c) 調(diào)度方案 (2, 1, 3)， 最后完成時間為 10 作業(yè) 2:3 作業(yè) 3:2 作業(yè) 1:2 空閑 :3 作業(yè) 2:1 機器 1 機器 2 作業(yè) 1:1 作業(yè) 3:3 (d) 調(diào)度方案 (2, 3, 1)， 最后完成時間為 9 算法設(shè)計與分析 清華大學出版社 作業(yè) 2:3 作業(yè) 3:2 作業(yè) 1:2 空閑 :2 作業(yè) 2:1 機器 1 機器 2 作業(yè) 1:1 作業(yè) 3:3 (e) 調(diào)度方案 (3, 1, 2)， 最后完成時間為 8 作業(yè) 2:3 作業(yè) 3:2 作業(yè) 1:2 空閑 :2 作業(yè) 2:1 機器 1 機器 2 作業(yè) 2:1 作業(yè) 3:3 (f) 調(diào)度方案 (3, 2, 1)， 最后完成時間為 8 算法設(shè)計與分析 清華大學出版社 算法 —— 批處理作業(yè)調(diào)度問題 void BatchJob(int n, int a[ ], int b[ ], int amp。 sum1[i]=0。 //初始迭代使用 k=1。 sum2[k]=max(sum1[k], sum2[k1])+b[x[k]]。 if (x[k]=n amp。amp。 } } } bool Ok(int k) //作業(yè) k與其他作業(yè)是否發(fā)生沖突 （ 重復 ） { for (i=1。 } 算法設(shè)計與分析 清華大學出版社 實驗項目 —— 0/1背包問題 1. 實驗題目 給定 n種物品和一個容量為 C的背包 ， 物品 i的重量是 wi，其價值為 vi， 0/1背包問題是如何選擇裝入背包的物品 （ 物品不可分割 ） ， 使得裝入背包中物品的總價值最大 ? 2. 實驗目的 （ 1） 掌握回溯法的設(shè)計思想； （ 2） 掌握解空間樹的構(gòu)造方法 ， 以及在求解過程中如何存儲求解路徑； （ 3） 考察回溯法求解問題的有效程度 。 i++) if (x[i]= =x[k]) return false。 x[k]=0。 kn) k=k+1。 else x[k]=x[k]+1。 while (k=1) { x[k]=x[k]+1。 } sum1[0]=0。 i=n?？梢宰C明，存在一個最優(yōu)作業(yè)調(diào)度使得在機器 1和機器 2上作業(yè)以相同次序完成。 i++) if (x[k]= =x[i] | | abs(ki)= =abs(x[k]x[i])) return false。 //放置下一個皇后 else { x[k]=0。 return。amp。 //在下一列放置第 k個皇后 while (x[k]=n amp。 i=n。 算法設(shè)計與分析 清華大學出版社 若兩個皇后擺放的位置分別是 (i, xi)和 (j, xj)， 在棋盤上斜率為 1的斜線上 ， 滿足條件 i－ j= xi－ xj， 在棋盤上斜率為 1的斜線上 ， 滿足條件 i＋ j= xi＋ xj， 綜合兩種情況 ，由于兩個皇后不能位于同一斜線上 ， 所以 ， 解向量 X必須滿足約束條件： |i－ xi|≠|(zhì)j－ xj| （ 式 ） 顯然 ， 棋盤的每一行上可以而且必須擺放一個皇后 ，所以 ， n皇后問題的可能解用一個 n元向量 X=(x1, x2, … , xn)表示 ， 其中 ， 1≤i≤n并且 1≤xi≤n， 即第 i個皇后放在第 i行第xi列上 。 k=k1。 kn ) { visited[x[k]]=1。 k++ ) coutx[k]。 k= =n amp。 c[x[k1]][x[k]]= =1) break。 x[1]=1。 i++) //初始化頂點數(shù)組和標志數(shù)組 { x[i]=0。amp。 visited[1]=1。amp。 k=k1。 } 算法設(shè)計與分析 清華大學出版社 else if (color[k]=m amp。 k= =n) //求解完畢 ， 輸出解 { for (i=1。 whi