工作分配问题-回溯法

问题

设有 n 件工作分配给 n 个人。将工作 i 分配给第 j 个人所需的费用为Cij
试设计一个算法，为每一个人都分配1件不同的工作，并使总费用达到最小。

Input

输入数据的第一行有1 个正整数n 。
接下来的n行，每行n个数，表示工作费用。

Output

将计算出的最小总费用输出。

Sample Input

3
10 2 3
2 3 4
3 4 5

Sample Output

9

分析

我们让每个工作选择一个人,每层dfs()表示工作m ,每个结点for循环表示被选择的人i ;
数组book[]记录人是都被选择分配了工作;
sum记录每个选择完后的费用总数;

AC代码

#include<iostream>#define N 9999using namespace std;int n;int sum=0,Min=N;int pay[N][N];int book[N];void dfs(int m) { //第m份工作if(m>n) {//工作分配完了 Min=min(Min,sum);//更新最小值 return;//结束 }for(int i=0; i<n; i++) { //第m份工作分给第i个人if(book[i]==0) {//如果第i个人没有被分配 book[i]=1;sum+=pay[m][i];if(sum<Min)//剪枝 dfs(m++);sum-=pay[m][i];//回溯 book[i]=0;}}}int main() {cin>>n;for(int i=0; i<n; i++) {for(int j=0; j<n; j++) {cin>>pay[i][j];}}dfs(1);cout<<Min<<"\n";}

代码分析

时间复杂度为O(n²)