工作分配问题【回溯算法】

  • Problem Description

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为 c i j c_{ij} cij。试设计一个算法,为每一个人都分配1件不同的工作,并使总费用达到最小。
设计一个算法,对于给定的工作费用,计算最佳工作分配方案,使总费用达到最小。

Input
输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行,每行n个数,表示工作费用。
Output
将计算出的最小总费用输出。

Sample Input

3
10 2 3
2 3 4
3 4 5

Sample Output

9
  • 解题思路

为工作 i 安排第 j 个人的解决方法与“运动员最佳匹配问题”类似,让一方选另一方,这样就可以构成一棵排列树。我们让工作“选”人,那排列树的结点代表人,而层就代表工作。如下图左上角的G1表示工人1,且在第一层,表示为工作 1 安排第 1 个人,即将工作1分配给工人1。

  • 样例分析

工作分配问题【回溯算法】_第1张图片

注:由上可知,最小值可能有多个,但效果一样,最终返回的都是9

  • 代码实现

#include 
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;
}
  • 运行结果工作分配问题【回溯算法】_第2张图片

你可能感兴趣的