分配人员（深搜未剪枝版）

题目描述

有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；
}