2. 从业资格
  3. 分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务多

分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务多

资格题库2022-08-02  60
问题 分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。为了花费时间最少，（   ）应该完成两项任务。A.甲B.乙C.丙D.丁
选项 A.甲
B.乙
C.丙
D.丁
答案 B
解析 本题考查的是动态规划。
任务指派问题，可用匈牙利算法。
假设增加一个人戊完成各项工作的时间取任务1、任务2、任务3、任务4、任务5最小值。
得效率矩阵为：
任务1任务2任务3任务4任务5
甲25?25 31 43?33
乙38?33 25 20?28
丙41?27 32 45?32
丁23 37?35?23?40
戊23 25 25?20?28
每一行元素减去该行的最小元素；得到如下矩阵：
0 0 6?18 8
18 13 5 0?8
14 0 5 18?5
0 14?12?0?17
3 5 5?0 8
没有0的列，减去该列的最小值：
0 0 1?18 3
18 13 0 0 3
14?0 0?18 0
0 14 12?0?12
3?5 0 0 3
找独立的【0】元素，
任务1任务2任务3任务4任务5
甲0（0）1?18 3
乙18 13（0）0 3
丙14?0 0?18（0）
丁（0）14?7?0 12
戊3 5?0（0）3
指派结果：
甲：任务2，25
乙：任务3、任务4，25、20
丙：任务5，32
丁：任务1，23
最少需要的时间为125。
故此题正确答案为B。
转载请注明原文地址:https://www.tihaiku.com/congyezige/2298487.html
本试题收录于： 高级信息系统项目管理师题库软件水平考试初中高级分类

高级信息系统项目管理师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)