小团的车辆调度

从别人手里蹭到的题目,O(N^3)的dp只得了18%分. Link: 美团点评2021秋招在线笔试（8.15场）

想到一个O(N^2)的解法,水一篇题解.

题目描述

小团是美团汽车租赁公司的调度师，某个时刻A和B两地都向该公司提交了租车的订单，分别需要a和b辆汽车。此时，公司的所有车辆都在外运营，通过北斗定位，可以得到所有车辆的位置，小团分别计算了每辆车前往A地和B地完成订单的利润。作为一名精明的调度师，当然是想让公司的利润最大化了。请你帮他分别选择a辆车完成A地的任务，选择b辆车完成B地的任务。使得公司获利最大，每辆车最多只能完成一地的任务。

输入描述

输入第一行包含三个整数n、a、b，分别表示公司的车辆数量和A、B两地订单所需数量，保证a+b<=n。（1<=n<=2000）接下来有n行,每行两个正整数x,y,分别表示该车完成A地任务的利润和B地任务的利润.

输出描述

输出仅包含一个正整数，表示公司最大获利的利润和。

样例输入

样例输出

题解排序+DP, O(N^2)

首先设m = a + b.

如果n=m,即刚好给定m辆车. 这种情况下,指派车辆问题很容易解决:

把m辆车按(x-y,x)降序排序,然后前a辆去A,后b辆去B.

但现在的问题是n>m. 我们依然可以扩展上面这个想法.

对n辆车按(x-y,x)降序排序, 对于任意一个给定的size=m的子序列(子集).我们知道前a辆车去A,后b辆车去B,是对于当前子集的最优分配方案.
那么现在新的问题是如何选出最优的子序列.

接下来我们使用DP来求最优子序列的问题,复杂度O(N^2).

dp[i][j]表示前i项里长度为j的子序列,并且固定前a项去A城市,能获取的最大收益.
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + (j <= a ? x[i] : y[i]))

Code: https://github.com/FiveEyes/FiveEyes.github.io/blob/master/assets/code/interview/driver_two_cities_assignment_problem.ipynb

题外话

这个题目其实是非常经典的Assignment Problem的一个变种…

KM算法的样本题. 但KM算法的复杂度是O(N^3)的,导致我想了很久如何去针对只有两个城市优化KM.
最大费最大流. 这个倒是可以优化一下,边数可以优化成O(N).但是费用流的复杂度一般是O(NMF)的,N是节点数,M是边数,F是最大流的大小.最后一样的来源是,费用流每次寻找一条单位流量且费用最大的增广路.
线性规划. 以上两个问题都可以归约成线性规划问题,这个双城的变形也只需要把每个工作限制人数从1扩展到a和b.但也没有想到如何加速…因为单纯形算法复杂度本身就没啥保障…