algorithm - 如何解决背包问题的这种变体？

Question

我正在尝试解决这个问题:有n位客户在邮局排队等待寄送包裹。 a[0], a[1], ..., a[n-1] 是第 1 个人到第 n 个人的 n 个客户的运费列表。邮政工作人员只需一分钟就可以完成客户寄送包裹所需的信息。然而，所有顾客都太忙，无法等待超过一定时间。 t[0], t[1], ..., t[n-1] 是 n 个客户中每个人可以在邮局花费的分钟列表。帮助邮政工作人员找到一种为顾客提供服务的方法，使邮局能够获得最大的资金，因为他们知道工作人员可以出于盈利的原因拒绝为某些顾客提供服务。)

示例:

• 对于 a = [10, 20, 5, 12], t = [2, 3, 3, 1]，输出应为 42。 说明:顾客的顺序是:第 4 个人 -> 第 1 个人 -> 第 2 个人(从 1 开始索引)
• 对于 a = [5, 1, 3, 2], t = [3, 1, 2, 2]，输出应为 10。 解释:虽然第二个人只能等待1分钟，但是这个人要付出的成本是最小的。因此，邮政工作人员不会为该顾客提供服务。顾客的顺序是:第3人->第4人->第1人。

我认为这是背包问题的一个变体，我可以使用蛮力来解决它，但仅限于小输入。有人可以帮我解决这个问题吗？谢谢。

Answer 1

如果没有重叠时间，问题就很简单，只需将所有运费相加即可。如果存在重叠，问题就变得非常重要。

因此，让我们形成一个(时间，成本)元组，并首先按时间排序，然后按成本(降序)排序。

例如输入:

a = [10, 20, 5, 12]
t = [2, 3, 3, 1]

元组的排序列表将是:

[(1, 12), (2, 10), (3, 20), (3, 5)]

现在让我们列出一份持续的成本 list 。

对于 (1,12)，我们的列表将为 [12]

对于 (2,10)，因为 2 不等于 1，您只需将成本 (10) 添加到您的列表 [12,10]

对于 (3,20)，因为 3 不等于 2，所以只需将 20 添加到列表中即可使其成为 [12,10,20]

对于 (3,5)，我们有重叠，有两个选项:

• 删除其中一项 - 列表中的最小值，即 10 并添加 5

• 跳过 5

  第二种选择会更好。 最终列表将是 [12,10,20]，其总和 = 42 就是答案。

请注意，列表的长度始终等于每次的时间 t。这是合乎逻辑的，因为您只能在时间 t 之前处理 t 个客户，而问题是如何在该列表中找到最佳成本。

让我们再举一个例子:

a = [10, 5, 7, 20, 15, 1]
t = [2, 2, 2, 3, 3, 1]

[(1, 1), (2, 10), (2, 7), (2, 5), (3, 20), (3, 15)]

对于这个，运行列表将如下所示:

t = 1 : [1] # 开始只需推送

t = 2 : [1, 10] # 2 > 1 所以推

t = 2 : [7, 10] # 2的重叠，看看是否可以删除1并添加7，是的所以推

t = 2 : [7, 10] # 重叠2个，看看是否可以去掉7，添加5，不行，因为会减少利润。所以保留这个列表。

t = 3 : [7, 10, 20] # 3 > 2，只需推

t = 3 : [10, 20, 15] #重叠3个，看看是否可以去掉min加15，可以的话去掉7加15。

答案是 45。

Python 中的代码如下所示:

import heapq
def get_max_shipping_cost(a, t):
    if len(a) == 0:
        return 0
    items = sorted(zip(t,a), key = lambda tup: (tup[0], -tup[1]))
    l = []
    heapq.heappush(l, items[0][1])
    s = items[0][1]
    i = 1
    prev = items[0]
    while i < len(items):
        if items[i][0] == prev[0]:
            prev = items[i]
            if s - l[0] + items[i][1] > s:
                s = s - l[0] + items[i][1]
                heapq.heappop(l)
                heapq.heappush(l,items[i][1])
            i += 1
        elif items[i][0] == prev[0] + 1:
            prev = items[i]
            heapq.heappush(l,items[i][1])
            s += items[i][1]
            i += 1
        else:
            prev = (prev[0] + 1, 0)
            heapq.heappush(l,0)
    return s