扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 动态规划中等
单选题
2023年5月第45题
收藏
分享
#数学与经济管理
#动态规划
#凯恩建议了解即可
#教材之外（超纲）
企业从部门中选择四个部门下月做甲、乙、丙、丁四项工作，每个部门做一项工作。已知每个部门做每项工作所需的成本(单位:万元)。
在总成本最低的方案中，（__）。
问题（1）
正确答案B
凯恩解析
本题考察的是最小成本分配 的求解思路。因为不是 n * n 的矩阵，所以不能用匈牙利算法。直接排除法来做。
这里可以固定选项中已指定的一对部门-工作，再在剩余部门与工作的二分匹配中取最小成本。
A选项：固定A→甲成本4，剩余{乙、丙、丁}在{B,C,D}间最优分配为B→丙6、C→乙9、D→丁10，总成本=4+6+9+10=29。不是最小。
B选项：固定A→乙成本7，剩余{甲、丙、丁}在{B,D,E}间最优分配为D→甲2、B→丙6、E→丁7，总成本=7+2+6+7=22。当前最小。
C选项：固定A→丙成本5，剩余{甲、乙、丁}在{B,C,E}间最优分配为B→甲5、C→乙9、E→丁7，总成本=5+5+9+7=26。大于22。
D选项：固定B→甲成本5，剩余{乙、丙、丁}在{C,D,E}间最优分配为C→丙7、E→丁7、D→乙12，总成本=5+7+7+12=31。大于22。
因此，总成本最低的方案为选项B。