1、實踐題目

工作分配問題

2、問題描述

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

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

輸出格式：將計算出的最小總費用輸出到屏幕。

輸入樣例：3

? ? ? ? ? ? ? ? ?10 2 3

? ? ? ? ? ? ? ? ? 2 3 4

? ? ? ? ? ? ? ? ? 3 4 5

輸出樣例：9

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

（1）解空間

解空間為{x1,x2,x3,······,xn}，其中xi=1,2,3,4···,n，表示第i個人安排的工作號。

（2）解空間樹：以n=3為例，解空間樹如下：

?

（3）剪枝方法

?算法中設置了一個數(shù)組，用來存放工作的完成狀態(tài)，當工作完成時設為1，否則設為0。

（4）具體代碼

1 #include<iostream> 2 using namespace std; 3 #define N 1000 4 int cost[N][N]; // 表示第i個人完成第j件工作需要的費用 5 int isC[N] = {0}; // 用于記錄第n個工作是否完成，0表示未完成 6 int n; 7 int scost; // 表示總費用 8 9 void Backstrack(int i, int c) 10 { 11 if(c > scost) return; 12 if(i == n) { // 當最后一個人也分配好工作后判斷總費用 13 if(c < scost) scost=c; 14 return; 15 } 16 for(int j=0;j<n;j++) { 17 if(isC[j]==0) { // 判斷第j個工作是否已經完成，類似剪枝函數(shù) 18 isC[j]=1; 19 Backstrack(i+1, c+cost[i][j]); 20 isC[j]=0; // 回溯法 21 } 22 } 23 } 24 25 int main() 26 { 27 cin>>n; 28 for(int i=0;i<n;i++) { 29 for(int j=0;j<n;j++) { 30 cin>>cost[i][j]; 31 } 32 } 33 scost = N; // 給總費用設置一個很大的值 34 Backstrack(0,0); 35 // 第一個0表示從第一個人開始 ，第二個0表示當前需要的總費用 36 cout<<scost; 37 return 0; 38 }

4、心得體會（對本次實踐收獲及疑惑進行總結）

這次實踐的過程中，可能是對回溯法還不是很了解，對剪枝函數(shù)或約束函數(shù)也不是很明白，所以在編程的過程中總是出現(xiàn)運行超時的問題，最后請教了同學，然后和結對編程小伙伴順利地解決了問題。總體上對于回溯算法的理解還并不是很透徹，還需要多實踐！

轉載于:https://www.cnblogs.com/CYUCHUN/p/10159596.html

總結

以上是生活随笔為你收集整理的回溯法解决工作分配问题及分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。