工作分布问题

正文索引 [隐藏]

题目描述:

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

输入描述:

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

输出描述:

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

输入样例:

3

10 2 3

2 3 4

3 4 5

输出样例:

9

解题思路:

回溯法。用minCost来记录最小总费用,将工作i分配给第j个人所需要的费用是c[i][j],用vis数组来标记工作是否被分配。用traceback函数来进行回溯,第一个参数表示当前在给第i个人找工作,第二个参数cnt表示当前总花费。若当前花费小于最小总花费,则对所有工作岗位进行遍历,把空余的工作交给i。当所有人都分配到了工作时,比较当前总花费是否小于最小总花费,若小于则对最小总花费进行更新。最后输出最小总花费即可。

代码:

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for (int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
const int INF = 0x3f3f3f3f;
const int maxn = 21;

int n,minCost = 0;
int c[maxn][maxn];     //将工作i分配给第j个人所需的费用为c[i][j]
bool vis[maxn];       //vis[i]用于标记第i个工作是否被分配

void traceback(int i,int cnt)   //回溯
{
    if(i>n && cnt<minCost)
    {
        minCost = cnt;
        return ;
    }
    if(cnt < minCost)
    {
        Up(j,1,n)
        {
            if(!vis[j])
            {
                vis[j] = true;
                traceback(i+1,cnt+c[i][j]);
                vis[j] = false;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    ms(c,INF);
    ms(vis,false);
    cin >> n;
    Up(i,1,n)
    {
        Up(j,1,n)
        {
            cin >> c[i][j];
            minCost += c[i][j];
        }
    }
    traceback(1,0);
    cout << minCost << endl;
    return 0;
}