分配人员（深搜剪枝版）

问题描述

有N个景点和N个导游，每个导游对每个景点熟悉程度不同，一个景点只需一个导游。求最大熟悉度。（0<=N<=17）

样例输入

4
1 2 3 4
4 3 2 1
2 3 4 1
2 4 3 1

样例输出

16

//本题算法是搜索，用深搜写，但是裸搜只有50分。

//下面就是智商高的看的剪枝了

//首先我们反向思维，将每个人对每个景点的熟悉度转换为不熟悉度（因为最多是1000，所以a[i,j]:=1000-a[i,j];即可）。

//至于用不熟练度去求是是为了能剪枝，因为如果只是比较熟悉度总和的最大值，过程中算出的当前值小于最大值并不能说明这个方案不能使用。但是比较不熟悉度总和的最小值时，在过程中当前值比现在的最小值大时就说明这种情况是不需要的（也就是说，这个情况搜下去，肯定没有我已得出的临时最优值大）。

//原标程中说用贪心求较优解，但是我仔细看了下，其实原标程中的z和min的初值其实就是1000*n。然后第一次搜索得到的值一定会将min更新，就会起到一个剪枝的作用。

#include<iostream>

using namespace std;

int n,now,minx;//n个导游,now为当前搜索得到的值,minx为最优值 
int a[100][100],b[100];//a[i][j]表示第j个导游对第i个景点的熟悉度
                       //b[i]表示第i个景点是否以被分配 

void go(int step){
    if(step==n+1){
        if(now<minx){
            minx=now;
            return;
        }
    }//如果分配完，尝试更新最优值 
    for(int i=1;i<=n;i++){
        if(b[i]==0&&now+a[i][step]<minx){//i景点是否已被分配与剪枝 
            now+=a[i][step];
            b[i]=1;//标记 
            go(step+1);//递归
            now-=a[i][step];
            b[i]=0;//回溯 
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) b[i]=0;//初始化b数组
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++){
        cin>>a[i][j];
        a[i][j]=1000-a[i][j];
      }//读入熟悉度，进行剪枝初始化 
    minx=1000*n;//初始化最优值 
    go(1);//深搜 
    cout<<n*1000-minx<<endl;//还原并输出；
    return 0; 
}