订单问题

订单问题

Description

Rahul and Ankit are the only two waiters in Royal Restaurant. Today, the restaurant received N orders. The amount of tips may differ when handled by different waiters, if Rahul takes the ith order, he would be tipped Ai rupees and if Ankit takes this order, the tip would be Bi rupees.In order to maximize the total tip value they decided to distribute the order among themselves. One order will be handled by one person only. Also, due to time constraints Rahul cannot take more than X orders and Ankit cannot take more than Y orders. It is guaranteed that X + Y is greater than or equal to N, which means that all the orders can be handled by either Rahul or Ankit. Find out the maximum possible amount of total tip money after processing all the orders.

(分配订单，A，B可以接固定数量的订单，每个订单A，B完成的价值不同，求最大分配价值)

思路

1. 在geek上看到一个O（nlogn）的解法，非常直接，对订单进行排序（订单对A的价值越大，对B的价值越小排前面，也就是说排序key= -(valueA[i]-valueB[i])），然后顺序分配订单给A，直到A的订单满了或者A完成当前订单的价值小于B时停止，剩下的订单分配给B。

2.就是动态规划

从第一个订单开始，把订单分配给A，或者B，递归剩下的订单，取两种分配的最大值。

`ans = max(valA[i] + f(i+1, ra-1, rb), valB[i] + f(i+1, ra, rb-1))`

其中valA表示A的价值数组，ra表示A还可以完成的订单，i表示当前任务index

参考实现（O(n^3))

from functools import lru_cache
def solve(X, Y, tx, ty):
    @lru_cache(None)
    def dfs(x, y, i):
        if i == len(tx):
            return 0
        if x == 0:
            return sum(ty[i:])
        elif y == 0:
            return sum(tx[i:])
        return max(tx[i]+dfs(x-1, y, i+1), ty[i] + dfs(x, y-1, i+1))
    return dfs(X, Y, 0)

完整代码

O_NJU_JK