当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ2369工作分配问题
4502+

题目大意:有n件工作分配给n个人,将工作i分配给第j个人所需的费用为cij,每个人分配一件工作,最小费用是多少?

题目描述

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法,为每一个人都分配一件不同的工作,并使总费用达到最小。

设计一个算法,对于给定的工作费用,计算最佳工作分配方案,使总费用达到最小。

输入

输入共两行,第一行有一个正整数n(1<=n<=20)。接下来的n行,每行n个数,第i行表示第i个人各项工作费用。

输出

输出最小总费用

样例输入

3 
4 2 5
2 3 6
3 4 5

样例输出

9

解题思路

格子填数类型的搜索题目,时间复杂度一般都是阶乘级别或者n次方级别的,数据量大了,不优化就会超时。

这里介绍两种优化方法:一是可行性剪枝,如果可行,我才继续搜索,如第9行,没分配过的工作才分配,重复分配是不可行的;二是最优性剪枝,算出来的结果比之前得到的更差,就不继续搜索,如第5行,当前的费用已经不低于最优费用了,那么后面再怎么分配工作都不会更好。

程序实现

SSOJ2369工作分配问题:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!