【正文】 if (x[k]=n amp。amp。 k= =n) { //得到一個(gè)解 ， 輸出 for (i=1。 i=n。 i++) coutx[i]。 return。 } 算法設(shè)計(jì)與分析 清華大學(xué)出版社 else if (x[k]=n amp。amp。 kn) k=k+1。 //放置下一個(gè)皇后 else { x[k]=0。 //重置 x[k]，回溯 k=k1。 } } } bool Place(int k) //考察皇后 k放置在 x[k]列是否發(fā)生沖突 { for (i=1。 ik。 i++) if (x[k]= =x[i] | | abs(ki)= =abs(x[k]x[i])) return false。 return true。 } 算法設(shè)計(jì)與分析 清華大學(xué)出版社 批處理作業(yè)調(diào)度問題 n個(gè)作業(yè) {1, 2, … , n}要在兩臺(tái)機(jī)器上處理 ， 每個(gè)作業(yè)必須先由機(jī)器 1處理 ， 然后再由機(jī)器 2處理 ，機(jī)器 1處理作業(yè) i所需時(shí)間為 ai， 機(jī)器 2處理作業(yè) i所需時(shí)間為 bi（ 1≤ i≤ n） ， 批處理作業(yè)調(diào)度問題要求確定這 n個(gè)作業(yè)的最優(yōu)處理順序 ， 使得從第 1個(gè)作業(yè)在機(jī)器 1上處理開始 ， 到最后一個(gè)作業(yè)在機(jī)器 2上處理結(jié)束所需時(shí)間最少 。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 顯然，批處理作業(yè)的一個(gè)最優(yōu)調(diào)度應(yīng)使機(jī)器 1沒有空閑時(shí)間，且機(jī)器 2的空閑時(shí)間最小?？梢宰C明，存在一個(gè)最優(yōu)作業(yè)調(diào)度使得在機(jī)器 1和機(jī)器 2上作業(yè)以相同次序完成。 例：三個(gè)作業(yè) {1, 2, 3}，這三個(gè)作業(yè)在機(jī)器 1上所需的處理時(shí)間為 (2, 3, 2)，在機(jī)器 2上所需的處理時(shí)間為 (1, 1, 3)，則最佳調(diào)度方案是 (1, 3, 2)、 (3, 1, 2)和 (3, 2, 1)，其完成時(shí)間為 8。 作業(yè) 1:2 作業(yè) 2:3 作業(yè) 3:2 空閑 :2 作業(yè) 1:1 機(jī)器 1 機(jī)器 2 作業(yè) 2:1 作業(yè) 3:3 (a) 調(diào)度方案 (1, 2, 3)， 最后完成時(shí)間為 10 作業(yè) 1:2 作業(yè) 2:3 作業(yè) 3:2 空閑 :2 作業(yè) 1:1 機(jī)器 1 機(jī)器 2 作業(yè) 2:1 作業(yè) 3:3 (b) 調(diào)度方案 (1, 3, 2)， 最后完成時(shí)間為 8 算法設(shè)計(jì)與分析 清華大學(xué)出版社 作業(yè) 2:3 作業(yè) 1:2 作業(yè) 3:2 空閑 作業(yè) 2:1 機(jī)器 1 機(jī)器 2 作業(yè) 1:1 作業(yè) 3:3 (c) 調(diào)度方案 (2, 1, 3)， 最后完成時(shí)間為 10 作業(yè) 2:3 作業(yè) 3:2 作業(yè) 1:2 空閑 :3 作業(yè) 2:1 機(jī)器 1 機(jī)器 2 作業(yè) 1:1 作業(yè) 3:3 (d) 調(diào)度方案 (2, 3, 1)， 最后完成時(shí)間為 9 算法設(shè)計(jì)與分析 清華大學(xué)出版社 作業(yè) 2:3 作業(yè) 3:2 作業(yè) 1:2 空閑 :2 作業(yè) 2:1 機(jī)器 1 機(jī)器 2 作業(yè) 1:1 作業(yè) 3:3 (e) 調(diào)度方案 (3, 1, 2)， 最后完成時(shí)間為 8 作業(yè) 2:3 作業(yè) 3:2 作業(yè) 1:2 空閑 :2 作業(yè) 2:1 機(jī)器 1 機(jī)器 2 作業(yè) 2:1 作業(yè) 3:3 (f) 調(diào)度方案 (3, 2, 1)， 最后完成時(shí)間為 8 算法設(shè)計(jì)與分析 清華大學(xué)出版社 算法 —— 批處理作業(yè)調(diào)度問題 void BatchJob(int n, int a[ ], int b[ ], int amp。bestTime) { //數(shù)組 x存儲(chǔ)具體的作業(yè)調(diào)度 ， 下標(biāo)從 1開始； //數(shù)組 sum1存儲(chǔ)機(jī)器 1的作業(yè)時(shí)間 ， //sum2存儲(chǔ)機(jī)器 2的作業(yè)時(shí)間 ， 下標(biāo)從 0開始 for (i=1。 i=n。 i++) { x[i]=0。 sum1[i]=0。 sum2[i]=0。 } sum1[0]=0。 sum2[0]=0。 //初始迭代使用 k=1。 bestTime=∞。 while (k=1) { x[k]=x[k]+1。 while (x[k]=n) if (Ok(k)) { sum1[k]=sum1[k1]+a[x[k]]。 sum2[k]=max(sum1[k], sum2[k1])+b[x[k]]。 if (sum2[k]bestTime) break。 else x[k]=x[k]+1。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 } else x[k]=x[k]+1。 if (x[k]=n amp。amp。 kn) k=k+1。 //安排下一個(gè)作業(yè) else { if (x[k]=n amp。amp。 k= =n) //得到一個(gè)作業(yè)安排 if (bestTimesum2[k]) bestTime=sum2[k]。 x[k]=0。 //重置 x[k]， 回溯 k=k1。 } } } bool Ok(int k) //作業(yè) k與其他作業(yè)是否發(fā)生沖突 （ 重復(fù) ） { for (i=1。 ik。 i++) if (x[i]= =x[k]) return false。 return true。 } 算法設(shè)計(jì)與分析 清華大學(xué)出版社 實(shí)驗(yàn)項(xiàng)目 —— 0/1背包問題 1. 實(shí)驗(yàn)題目 給定 n種物品和一個(gè)容量為 C的背包 ， 物品 i的重量是 wi，其價(jià)值為 vi， 0/1背包問題是如何選擇裝入背包的物品 （ 物品不可分割 ） ， 使得裝入背包中物品的總價(jià)值最大 ? 2. 實(shí)驗(yàn)?zāi)康? （ 1） 掌握回溯法的設(shè)計(jì)思想； （ 2） 掌握解空間樹的構(gòu)造方法 ， 以及在求解過程中如何存儲(chǔ)求解路徑； （ 3） 考察回溯法求解問題的有效程度 。 算法設(shè)計(jì)與分析 清華大學(xué)出版社 3. 實(shí)驗(yàn)要求 （ 1） 設(shè)計(jì)可能解的表示方式 ， 構(gòu)成解空間樹； （ 2） 設(shè)計(jì)回溯算法完成問題求解； （ 3） 設(shè)計(jì)測(cè)試數(shù)據(jù) ， 統(tǒng)計(jì)搜索空間的結(jié)點(diǎn)數(shù)；