如何解决背包问题的这种变体? [英] How to solve this variant of the Knapsack problem?

问题描述

我正在尝试解决此问题:邮局中有 n个客户排队等候发送包裹. a [0]，a [1]，...，a [n-1] 是n位客户从第一个人到第n个人的运输成本的列表.邮政工作人员需要一分钟的时间来完成客户发送包裹所需的信息.但是，所有客户都忙于等待一段时间. t [0]，t [1]，...，t [n-1] 是n位客户可以在邮局消费的分钟数列表.帮助邮政工作人员找到一种服务客户的方法，以便使邮局获得最大的收益，同时要知道允许该工作人员出于盈利的理由拒绝为某些客户提供服务.)

I am trying to solve this problem: There are n customers queuing at post office to wait to send parcels. a[0], a[1], ..., a[n-1] is the list of shipping costs of n customers from the 1st to the nth person. It takes exactly a minute for the postal worker to complete the information needed for a customer to send a parcel. However, all customers are too busy to wait for more than a certain period of time. t[0], t[1], ..., t[n-1] is the list of minutes each of n customers can spend at the post office. Help the postal worker to find a way to serve customers so that the post office can get the largest amount of money, knowing that the staff is allowed to refuse to serve some customers for the profitable reason.)

示例:

• 对于 a = [10，20，5，12]，t = [2，3，3，1] ，输出应为 42 .说明:客户的订单是:第四人->第一人称->第二个人(基于1的索引)
• 对于 a = [5，1，3，2]，t = [3，1，2，2] ，输出应为 10 .说明:尽管第二个人只能等待1分钟，但该个人必须支付最少的费用.因此，邮政工作人员将不会为该客户提供服务.客户的订单是:第三人->第四个人->第一人称.

• For a = [10, 20, 5, 12], t = [2, 3, 3, 1], the output should be 42. Explanation: The order of the customers is: the 4th person -> the 1st person -> the 2nd person (1-based indexing)
• For a = [5, 1, 3, 2], t = [3, 1, 2, 2], the output should be 10. Explanation: Although the 2nd person can wait only 1 minute, this person has to pay the smallest cost. Therefore, the postal worker will not serve this customer. The order of the customers is: the 3rd person -> the 4th person -> the 1st person.

我认为这是背包问题的一种变体，我可以使用蛮力解决它，但仅适用于少量输入.有人可以帮我解决这个问题吗?谢谢.

I think it is a variant of the knapsack problem, I can solve it by using brute force but only for small input. Can someone help me to solve this problem? Thanks.

推荐答案

如果没有重叠的时间，那么问题很简单，那就是总结所有的运输成本.如果有重叠，这个问题就变得很简单.

If there are no overlapping times, the problem is straightforward just sum up all the shipping costs. The problem becomes non-trivial if there is overlap.

因此，让我们形成(时间，成本)的元组，然后先按时间然后按成本(降序)对它们进行排序.

So lets form a tuple of the (time, cost) and sort them first by time and then by cost(descending).

例如输入:

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

元组的排序列表将是:

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

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

Now lets have a running list of costs.

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

For (1,12) our list will be [12]

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

For (2,10) because 2 is not equal to 1, you can just add the cost (10) to your list [12,10]

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

For (3,20) because 3 is not equal to 2, you just add 20 to the list to make it [12,10,20]

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

For (3,5) we have an overlap there are two options:

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

• get rid of one of the items - the minimum of the list i.e. 10 and add 5

跳过5

第二种选择会更好.最终的列表将是[12,10,20]，总和为42.

The second option will be better. The final list will be [12,10,20] whose sum = 42 is the answer.

请注意，列表的长度始终等于每次的时间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)]

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

For this one the running list will look like:

t = 1:[1]#仅从推入开始

t = 1 : [1] # Beginning just push

t = 2:[1，10]#2>1按下

t = 2 : [1, 10] # 2 > 1 so push

t = 2:[7，10]#2的重叠部分，看看是否可以删除1和可以添加7是，所以按

t = 2 : [7, 10] # overlap of 2, see if 1 can be removed and 7 can be added yes so push

t = 2:[7，10]#2的重叠，看看是否可以删除7和可以添加5，否，因为这会减少利润.因此，保留列表.

t = 2 : [7, 10] # overlap of 2, see if 7 can be removed and 5 can be added, no because it will reduce the profit. So keep the list.

t = 3:[7，10，20]#3>2，只要按下

t = 3 : [7, 10, 20] # 3 > 2, just push

t = 3:[10，20，15]#重叠3，看看是否可以删除最小值并可以添加15，是，然后删除7并添加15.

t = 3 : [10, 20, 15] # overlap of 3, see if the min can be removed and 15 can be added, yes then remove 7 and add 15.

答案是45.

python中的代码如下:

Code in python looks like:

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

这篇关于如何解决背包问题的这种变体?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！