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

Question

我正在尝试解决这个问题：在post办公室有n customers排队等待寄送包裹。 a[0], a[1], ..., a[n-1]是n个客户从第1人到第n人的运费清单。 postal 工作人员只需一分钟即可完成客户发送包裹所需的信息。然而，所有的顾客都太忙了，不能等待超过一定的时间。 t[0], t[1], ..., t[n-1] 是 n 个客户中每个人可以在 post 办公室度过的分钟列表。帮助 postal 员工找到服务客户的方法，使 post 办公室可以获得最大的收益，因为他们知道员工可以出于盈利原因拒绝为某些客户提供服务。 )

示例：

对于a = [10, 20, 5, 12], t = [2, 3, 3, 1]，输出应该是42。解释：顾客的顺序是：第4人->第1人->第2人（1-based indexing）
对于a = [5, 1, 3, 2], t = [3, 1, 2, 2]，输出应该是10。解释：虽然第 2 个人只能等 1 分钟，但这个人要付出最小的代价。因此，postal 工作人员将不会为该客户提供服务。客人的顺序是：第3人->第4人->第1人

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

Answer 1

如果没有重叠时间，问题就简单了，把所有的运费加起来就可以了。如果有重叠，问题就变得很重要。

所以让我们形成一个 (time, cost) 的元组，然后先按时间排序，然后按成本（降序）排序。

例如输入：

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

排序后的元组列表将是：

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

现在让我们有一个运行成本清单。

对于 (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] # 刚开始 push

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

t = 2 : [7, 10] # 2的重叠，看能不能去掉1，能不能加7 yes so push

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

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

How to solve this variant of the Knapsack problem?

algorithm

knapsack-problem

dynamic-programming