讨论/技术交流/各位大佬,请问这个类似排队的问题要用什么算法来解啊/
各位大佬,请问这个类似排队的问题要用什么算法来解啊

题目

现有n个人,要做m个任务,每个人都要把所有任务做一遍,同一任务同一时间只能一个人做,第i人做任务所需时间为T[i] = [t1,t2,t3, ... ,tm] 求1任务分配方案,使得所有人完成任务所需时间最少

例子
现有甲乙丙丁戊5人,有ABC三个任务,要求所有人分别把ABC任务做完,其中每个任务同一时间只能由一人来做,现甲乙丙做ABC任务需要[2,3,4] 分钟,丁戊做ABC任务需要[3,5,6] 分钟,(任务不能拆分,即不可甲先做A1分钟,再由乙做A,然后甲再做A1分钟)
求分配方案,使得时间最少

请问要用什么算法?如有解法思路过好,感谢各位大佬

2
共 4 个回复

感谢回复
穷举的话肯定是不行的了,时间上做不了
贪心算法的话,确实是最近的方法了,但试了几组数据,感觉差距有点大。。。
有没有可能拆分为几个问题分别求解呢

搞不定,这道题目肯定不是一个算法题,而是工作中遇到的问题吧。就算有解法,解法也肯定不可能是多项式时间复杂度的。

给一个正确性没问题的算法。对每个任务,暴力枚举完成它的人的排列,同时对每个人暴力枚举他完成的任务的排列。这样就可以得到一个唯一的执行流程(当然也可能冲突),这样需要暴力枚举的次数就是O((n!)m(m!)n)O((n!)^m(m!)^n)。但是肯定不能满足你的数据范围要求。

如果只需要近似解,可以直接贪心,每次一个任务空出,就找一个剩余工作时间最多的人来做它就好了。

感谢回复
任务顺序随便做
数据范围人数30以下,任务20以下即可

没看懂题目意思,任务必须按顺序做吗。数据范围多大?