题目描述
有n个人从事n项工作，每个人只能从事一项，程序读入他们做每个工作的效益，求最佳安排使效益最高
输入文件
第一行为n，以下n*n为。。。（如题）
输出文件
两行，第一行第i个数表示第i个人从事的工作，第二行为最优情况下的效率的总和
#include<iostream>
using namespace std;
int data[10][10];
int f[10],g[10],p[10];//f为深搜中当前的人员分配,g中为当前最优的人员分配方案,p用1/0表示第i份工作是否被做
int n,maxl,now;//now为当前的效率总和，maxl为当前最优值
void go(int step){
if(step==n+1){
if(now>maxl){
maxl=now;
for(int i=1;i<=n;i++) g[i]=f[i];
}
return;
}//判断是否分配完成,并尝试更新最优值
for(int i=1;i<=n;i++){
if(p[i]==0){
f[step]=I; p[i]=1; now+=data[step][i];//标记
go(step+1);
now-=data[step][i];
p[i]=0;//回溯
}
}
}
int main(){
maxl=0; cin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
cin>>data[i][j];
for (int i=1;i<=n;i++) p[i]=0;//初始化
go(1);
for(int i=1;i<n;i++) cout<<g[i]<<" ";
cout<<g[n]<<endl;
cout<<maxl<<endl;//输出最优解
return 0；
}
