首页 > 试题广场 >

订单分配

[编程题]订单分配

打车派单场景, 假定有N个订单，待分配给N个司机。每个订单在匹配司机前，会对候选司机进行打分，打分的结果保存在N*N的矩阵A，其中Aij 代表订单i司机j匹配的分值。

假定每个订单只能派给一位司机，司机只能分配到一个订单。求最终的派单结果，使得匹配的订单和司机的分值累加起来最大，并且所有订单得到分配。

第一行包含一个整数N，2≤N≤10。

第二行至第N+1行包含N*N的矩阵。

输出分值累加结果和匹配列表，结果四舍五入保留小数点后两位
（注意如果有多组派单方式得到的结果相同，则有限为编号小的司机分配编号小的订单，比如：司机1得到1号单，司机2得到2号单，就比司机1得到2号单，司机2得到1号单要好）

示例1

输入

3
1.08 1.25 1.5
1.5 1.35  1.75
1.22 1.48 2.5

第一行代表得到的最大分值累加结果5.25，四舍五入保留两位小数；

第二行至第四行代表匹配的结果[i j],其中i按行递增：

订单1被派给司机2，订单2被派给司机1，订单3被派给司机3。使得A12+ A21+ A33= 1.25 + 1.5 + 2.5 = 5.25在所有的组合中最大。

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

C++工程师美团 2020 Java工程师

上传者：小小

难度：

0条回答 84收藏 6872浏览

订单分配

扫一扫，把题目装进口袋