工作分配问题

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

Input
第一行有1个正整数n (1≤n≤20)。接下来的n行，每行n个数，第i行表示第i个人各项工作费用。
Output
最小总费用。

Sample Input
3
4 2 5
2 3 6
3 4 5

Sample Output
9

#include <bits/stdc++.h>
using namespace std;
int a[25][25],b[25];//数组b来判断是否此人已选工作
int n,s,sum;//sum来存最小费用
void dfs(int x,int y)
{
s+=a[x][y];
b[y]=1;
if(s>=sum) return; //防止超时
if(x==n){
if(s<sum) sum=s;
return;
}
for(int i=1;i<=n;i++){
if(!b[i]){
dfs(x+1,i);
s-=a[x+1][i];//回溯
b[i]=0;
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF){
s=0;
sum=1e9;
memset(b,0,25*sizeof(int));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(0,0);
cout<<sum<<endl;
}
return 0;
}在这里插入代码片

最后

以上就是温婉夏天为你收集整理的工作分配问题的全部内容，希望文章能够帮你解决工作分配问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。