当前位置:首页 > 搜索 > 深度优先搜索 > 正文
SSOJ2367最佳调度问题
6932+

题目大意:n个任务分给m个机器完成,现在告诉你各个人物需要的时间,请问最早什么时候完成?

题目描述

假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti.试设计一个算法找出完成这n个任务的最佳调度,使得完成全部任务的时间最早。

编程任务:

对任意给定的整数n和k ,以及完成任务i需要的时间为ti,i=1~n。编程计算完成这n个任务的最佳调度。

输入

第一行有2个正整数n和k;第2行的n个正整数是完成n个任务需要的时间。(n<20)

输出

输出完成全部任务的最早时间

样例输入

7 3
2 14 4 16 6 5 3

样例输出

17

解题思路

填n个格子,每个格子填一个机器的编号,怎么填都可行,所有格子填完后,各个机器都有完成任务的总时间,取最大者。枚举所有方案,最小的那个方案即是答案,时间复杂度O(mn),不优化绝对超时。

优化1:最优化剪枝——如果当前方案有任一个机器超过已有的最短时间,停止搜索。

首先,为了让这个“最短时间”快点出现,我们可以用贪心得到一个较优解,如代码中的37-49行就是这个步骤,如果你想写那么长,不优化的话就直接写ans=1e9;其次,如果任意机器时间超过“最短时间”,就不要往下看了,如代码中的第15行,只有不超过“最短时间”才继续搜索。

优化2:排序——让大任务先选机器,这样后面选选择会少很多。

如剩下任务所需时间分别是“9 6 4 3”,当前最短时间是12,选了9之后就只能再选3,剩下4和9一组;如果你先选3,3可以跟4组合也可以跟6组合,搜索的解更多了。(从小到大安排任务有好处吗?可以试试、想想)

优化3:去重——搜索中出现很多重复问题,如第一个任务放在机器1、机器2、……、机器m是等价的。

最简单的,规定第一个任务只能放在机器1,这样时间就可以除以m了。但还是有很多很多重复!如第2个机器,可以放在机器2、机器3……怎么样更好地解决重复问题呢?我们可以考虑一下最终的答案,并让其有一点顺序:对于最优解,必定存在各个机器上分配好任务的,我们可以按照各个机器的最大任务时间从大到小排,机器里的任务也从大到小排,搜索时,如果出现下一个机器的最大任务时间比前一个大,说明他是重复的,不继续搜索,这样就大大减少了单个任务跳来跳去的重复问题了。程序中第16-19和23、49行,就是处理重复问题,每个机器进去的第一个任务,必是该机器的最大任务(从大到小依次处理任务的好处),如果比前面的大,不用重复搜索,否则记录下该机器的最大任务时间。

其他优化:做一下小木棍。

程序实现

SSOJ2367最佳调度问题:等您坐沙发呢!

发表评论

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