How to solve this variant of the Knapsack problem?

Question

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.)

Example:

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.

user_1410303 · Answer

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).

For example for the input:

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

the sorted list of tuples will be:

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

Now lets have a running list of costs.

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

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

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

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

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

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

Note here the length of the list is always equal to the time t at each time. This is logical because you can only process t customers up to time t and the problem is to fit the best costs with in that list.

Lets take another example:

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] # Beginning just push

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

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] # 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, just push

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.

The answer will be 45 for this.

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

How to solve this variant of the Knapsack problem?

1 Answers