设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。 设计一个算法,对于给定的工作费用,为每一个人都分配1 件不同的工作,并使总费用达到最小。1<=n<=20
可以回溯搜索全部分配方案,然后比较出费用最小的方案。
中间可以优化,如果工作还未分配完但此时费用已超过当前保存的最小值,可以直接跳过这种方案
#include<bits/stdc++.h>
using namespace std;
int n,a[21][21];
bool f[21]={0},sum=10000000,tem=0;//f用于判断该项工作是否已被分配
void se(int t){
if(t==n+1&&tem<sum) sum=tem;
for(int i=1;i<=n;i++){//i是第i项工作
if(f[i]==0){
tem+=a[t][i];
f[i]=1;
if(tem<sum) se(t+1);//跳过当前方案
tem=tem-a[t][i];
f[i]=0;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
se(1);
printf("%d",sum);
return 0;
}