扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 动态规划困难
单选题
2015年11月第46题
困难
单选题
2015年11月第46题
#了解即可
#超纲
甲、乙、丙、丁4人加工A、B 、C、D四种工件所需工时如下表所示。指派每人加工一种工件,四人加工四种工件其总工时最短的最优方案中,工件B应由(__)加工。

问题(1)
正确答案
D
本题考察的是指派问题(Assignment Problem)中的匈牙利算法或最优化分配方法。
目标是让四位工人分别安排到不同的岗位,使得总工时最小,这属于典型的最小化成本的指派问题。
第一步:行最小值减法(行归约),对每一行,减去该行的最小值。
甲:14 9 4 15 → 减4 → 10 5 0 11
乙:11 7 7 10 → 减7 → 4 0 0 3
丙:13 2 10 5 → 减2 → 11 0 8 3
丁:17 9 15 13 → 减9 → 8 0 6 4

第二步:每列减去该列最小值
A列:10 4 11 8 → 减4 → 6 0 7 4
B列:5 0 0 0 → 减0 → 保持不变
C列:0 0 8 6 → 减0 → 保持不变
D列:11 3 3 4 → 减3 → 8 0 0 1

第三步:寻找独立0 构造最优匹配
找到4个不同行不列的0组成完美匹配。

可以看到 B 工件由丁加工。
