算法第五章实践报告
1、实践题目 ：工作分配问题
2、问题描述
设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。 设计一个算法，对于给定的工作费用，为每一个人都分配1 件不同的工作，并使总费用达到最小。
输入：输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。
输出：将计算出的最小总费用输出到屏幕。
3、算法描述（包括解空间，画出测试样例的解空间树，剪枝（约束函数或限界函数）方法描述）
1 #include<iostream> 2 using namespace std; 3 4 int minExp =0 ; //初始化当前费用和最小费用为0 5 int n ; //n个人n件工作 6 int a[50][50] ; 7 int x[50] ; 8 9 10 void backtrace(int i , int cexp){ //第i个工作 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个人是否有工作 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个人做第j份工作的费用 34 x[j] = 0 ; 35 } 36 minExp+=a[i][i] ; 37 } 38 39 backtrace(1,0) ; //从第一个人开始遍历 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）}
约束函数：
x[j] == 0
即第j个人是否有工作
限界函数：
cexp < minExp
即当前费用小于最小费用
4、心得体会（对本次实践收获及疑惑进行总结）
刚开始做这道题想用数组交换元素的方法做，但是发现结果不对，其实这道题可以这样想：设置一个数组x[]来记录每个人是否有工作，每分配一份工作就从头遍历一次询问该元素i的x[i]是否为0，是则将该工作分配给他，再通过回溯来搜索出所有的情况，出来的代码比较简单。第二个要注意的是最小工作费用的初始化问题，由于遍历解空间树时第一条路径是（1,2,3）所以最小工作费用可以初始化为a[1][1]+a[2][2]+a[3][3]。这道题的解空间树属于排列树，也让我更加熟练掌握回溯法中排列树的算法思路和框架。