首页 > 试题广场 >

工作分配问题:设有 n 件工作分配给n 个人。将工作

[问答题]
工作分配问题:设有 n 件工作分配给n 个人。将工作i 分配给第j 个人所需费用为Cij 。试设计一个算法,为每一个人分配一件不同的工作,并使总费用达到最小。
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

int n;
int minV = INT_MAX;
void brackTracking(int floor,vector<bool> x,vector<vector<int>> c,int curV)
{

    if(floor > n)
    {
        minV = curV<minV?curV:minV;
    }

    for(int i = 1;i<=n;i++)
    {
        if(!x[i])
        {
            curV += c[floor][i];
            x[i] = 1;
            if(curV < minV) brackTracking(floor+1,x,c,curV);
            curV -= c[floor][i];
            x[i] = 0;
        }
    }

}

int main()
{
    cin>>n;
    vector<vector<int>> c(n+1,vector<int>(n+1,0));
    vector<bool> x(n+1,0);
    for(int i = 1;i<=n;i++)
    {
        for(int j = 1;j<=n;j++)
        {
            cin>>c[i][j];
        }
    }
    int curV = 0;
    brackTracking(1,x,c,curV);
    cout<<minV<<endl;
    return 0;
}


发表于 2023-11-06 16:37:23 回复(0)