?

1、實(shí)踐題目 ：工作分配問(wèn)題

?

2、問(wèn)題描述

設(shè)有n件工作分配給n個(gè)人。將工作i分配給第j個(gè)人所需的費(fèi)用為cij 。 設(shè)計(jì)一個(gè)算法，對(duì)于給定的工作費(fèi)用，為每一個(gè)人都分配1 件不同的工作，并使總費(fèi)用達(dá)到最小。

輸入：輸入數(shù)據(jù)的第一行有1 個(gè)正整數(shù)n (1≤n≤20)。接下來(lái)的n行，每行n個(gè)數(shù)，表示工作費(fèi)用。

輸出：將計(jì)算出的最小總費(fèi)用輸出到屏幕。

?

3、算法描述（包括解空間，畫(huà)出測(cè)試樣例的解空間樹(shù)，剪枝（約束函數(shù)或限界函數(shù)）方法描述）

1 #include<iostream> 2 using namespace std; 3 4 int minExp =0 ; //初始化當(dāng)前費(fèi)用和最小費(fèi)用為0 5 int n ; //n個(gè)人n件工作 6 int a[50][50] ; 7 int x[50] ; 8 9 10 void backtrace(int i , int cexp){ //第i個(gè)工作 11 12 13 if(i > n ){ 14 if(cexp < minExp) minExp = cexp; 15 return ; 16 } 17 if(cexp < minExp){ 18 for(int j = 1 ; j <= n ; j++){ 19 if(x[j] == 0){ //第j個(gè)人是否有工作 20 x[j] = 1 ; 21 backtrace(i+1 , cexp + a[i][j]) ; 22 x[j] = 0 ; 23 } 24 } 25 } 26 } 27 int main() 28 { 29 cin >> n ; 30 31 for(int i=1 ; i<=n ; i++){ 32 for(int j=1 ; j<=n ; j++){ 33 cin >> a[i][j] ; //第i個(gè)人做第j份工作的費(fèi)用 34 x[j] = 0 ; 35 } 36 minExp+=a[i][i] ; 37 } 38 39 backtrace(1,0) ; //從第一個(gè)人開(kāi)始遍歷 40 cout << minExp ; 41 42 return 0; 43 }

?解空間為：{（1,2,3），（1,3,2），（2,1,3），（2,3,1）,（3,1,2），（3,2,1）}

?約束函數(shù)：

x[j] == 0

即第j個(gè)人是否有工作 限界函數(shù)：
cexp < minExp 即當(dāng)前費(fèi)用小于最小費(fèi)用

?

4、心得體會(huì)（對(duì)本次實(shí)踐收獲及疑惑進(jìn)行總結(jié)）

剛開(kāi)始做這道題想用數(shù)組交換元素的方法做，但是發(fā)現(xiàn)結(jié)果不對(duì)，其實(shí)這道題可以這樣想：設(shè)置一個(gè)數(shù)組x[]來(lái)記錄每個(gè)人是否有工作，每分配一份工作就從頭遍歷一次詢(xún)問(wèn)該元素i的x[i]是否為0，是則將該工作分配給他，再通過(guò)回溯來(lái)搜索出所有的情況，出來(lái)的代碼比較簡(jiǎn)單。第二個(gè)要注意的是最小工作費(fèi)用的初始化問(wèn)題，由于遍歷解空間樹(shù)時(shí)第一條路徑是（1,2,3）所以最小工作費(fèi)用可以初始化為a[1][1]+a[2][2]+a[3][3]。這道題的解空間樹(shù)屬于排列樹(shù)，也讓我更加熟練掌握回溯法中排列樹(shù)的算法思路和框架。

轉(zhuǎn)載于:https://www.cnblogs.com/hwy1003213/p/10170586.html

總結(jié)

以上是生活随笔為你收集整理的算法第五章实践报告的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。