查看更多
当前 - 选择题 - 动态规划
中等
单选题
2023年5月第45题
#了解即可
#超纲

企业从部门中选择四个部门下月做甲、乙、丙、丁四项工作,每个部门做一项工作。已知每个部门做每项工作所需的成本(单位:万元)。
在总成本最低的方案中,(__)。

问题(1)
浓缩知识点

多任务多资源的最小成本分配问题中,当资源与任务数量不匹配即成本矩阵非n×n形式时,无法直接使用针对方阵的匈牙利算法求解。此时可采用固定局部匹配结合剩余资源任务最优分配的策略:先选定一组资源与任务的配对,再在剩余的资源和任务集合内,为每个任务匹配对应成本最低的可用资源,累加得到该方案的总成本;通过枚举不同的初始固定配对方案,对比各方案的总成本数值,即可确定全局最优的低成本分配方案。这类策略在资源与任务规模较小的场景中效率较高,若面对大规模匹配问题,可结合贪心算法思路逐步匹配,但需注意单纯贪心策略可能仅得到局部最优解,小规模场景下枚举固定点再计算剩余最优的方式更易得到全局最优结果。

正确答案
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

联系我们
隐私协议
用户协议
微信公众号
知乎
小红书
浙ICP备2021029036号
@2022-2026
嘉兴市安芯网络科技有限公司 版权所有