【回溯法】工作分配

本文主要是介绍【回溯法】工作分配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

有$n$项工作要分配给$n$个人完成，每个人只能从事一项工作，且每项工作只能由一人完成。已知第$i$个人完成第$j$项工作的工费是$c[i][j]$元，那么怎么给每个人分配工作才能使得总工费最小。

输入格式

一个整数$n$，接下来的$n$行，每行一个$10000$以内的正整数，其中第$i+1$行第$j$列的整数 ,表示第$i$个人完成第$j$项工作时的工费。

输出格式

输出一个整数，表示最小的总工费。

样例输入

3
6 5 4
4 3 2
1 5 2

样例输出

8

数据范围提示

$2<=n<=20$

题解

此题使用回溯法即可，由于只求最优解，需要使用限界条件，这里选定限界条件为$curCost+leaf[i]<cost$。
其中，$curCost$表示当前递归到第$i$层所用消耗，$$leaf[i]=\sum _{k=i}^n\underset{1\le j\le n}{\min }c\left[k\right]\left[j\right]$$

代码

#include <iostream>
#include <algorithm>
using namespace std;
int visit[21];//访问标记数组
int num[21][21];//输入数据
int leaf[21];//限界数组
int n;//长度n
int cost=1e9;//最大消耗
void calc(int curCost,int index){//递归层数从1到n+1，n+1层判断是否为最小值if(index>n&&curCost<cost){cost=curCost;return;}//限界条件curCost+leaf[index]<cost//如果后续点的最小消耗值小于当前消耗最小值if(curCost+leaf[index]<cost)for(int i=1;i<=n;i++){//若该点未访问，访问该点if(!visit[i]){visit[i]=1;calc(curCost+num[index][i],index+1);visit[i]=0;}}
}
int main() {freopen("B.in","r",stdin);freopen("B.out","w",stdout);scanf("%d",&n);//输入数据for(int i=1;i<=n;i++){visit[i]=0;for(int j=1;j<=n;j++) scanf("%d",&num[i][j]);}//用动态规划计算从i点开始到最后一个点的最低消耗值//结果保存在leaf[i]for(int i=n;i>=1;i--){leaf[i]=num[i][1];for(int j=2;j<=n;j++){leaf[i]=min(leaf[i],num[i][j]);}if(i!=n) leaf[i]+=leaf[i+1];}//调用求解函数calc(0,1);printf("%d",cost);return 0;
}

这篇关于【回溯法】工作分配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---