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

输入格式

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

输出格式

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

输入样例

在这里给出一组输入。例如：

1
2
3
4
3
10 2 3
2 3 4
3 4 5

输出样例

在这里给出相应的输出。例如：

1
9

解题思路

通过分析问题可知，要使用回溯算法解决该问题，可以看出此问题的解空间树这是一个典型的排列树。

采用递归回溯的方法，同样用book[ ] 进行记录，数组中的下标 i 表示第几个人，book[i]=0表示没有被分配工作；book[i]=1表示已经被分配工作。

t 表示第几份工作，排序树的层数（也就是递归的层数）代表这是第几个工作

其实本题就是确定这三个人的排序，谁做第一个，第二个，第三个工作，核心是全排列算法，确定排序，求时间总和，进而得到最小时间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;

int n;
int pay[21][21];   //pay[i][j]表示将工作i分配给第j个人的费用为pay[i][j]
int Min=INT_MAX;   //因为要求最小值，所以将Min初始化为最大整数（int型）
int sum=0;   //记录搜索过程中得到的工作费用和
int book[21];   //用于标记一个人是否已被分配工作：book[i]=0表示没有被分配工作；book[i]=1表示已经被分配工作

void dfs(int t)
{
    if(t>=n)   //已经到达叶子结点，继续判断是否找到了最小总费用
    {
        if(Min>sum)   //没有找到最小总费用
        {
            Min=sum;   //更新最小总费用
            return;
        }
    }
    for(int i=0;i<n;i++)   //为第工作t安排人
    {
        if(!book[i])   //第i个人还没有被安排工作
        {
            book[i]=1;   //将工作t分配给第i个人
            sum+=pay[t][i];   //更新总费用
            if(sum<Min)   //如果当前得到的sum小于最小值，就向下搜索子树；否则剪枝
                dfs(t+1);
            book[i]=0;   //没有得到比Min更小的和，回溯
            sum-=pay[t][i];
        }
    }

}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>pay[i][j];
        }
        book[i]=0;
    }
    dfs(0);
    cout<<Min<<endl;
    return 0;
}