DIFFICULTY:
MEDIUM
PROBLEM:
There are NN items in the bakery. Each item’s cost is cost[i]cost[i] and the delivery charge is delivery_cost[i]delivery_cost[i] for ii = 00 to NN respectively. The chef wants to select exactly MM items to sell in a way that the total cost is maximized.
The total cost for any set of items is the sum of costs of those items + (minimum delivery cost among those items * total no. of items)
. Help the chef find the maximum cost for MM items.
EXPLANATION
There are two major ways to think about this problem. One is a backtracking-based approach and the other is a heap-based approach.
1. Backtracking:
The main idea of this approach is to try all the possibilities using recursion and use memorization to overcome repeated computations.
SOLUTION
import sys
min_d = 10 ** 7
# set recursion limit
sys.setrecursionlimit(10 ** 7)
# argument mid_d_cost maps to the minimum delivery cost
# among the current set of items in the bag.
def recurce(i, bag_size, min_d_cost):
# base cases
if bag_size == 0: return min_d_cost * m
if i >= n: return 0
if (i, bag_size, min_d_cost) in DP:
return DP[(i, bag_size, min_d_cost)]
k = max(
cost[i] + recurce(i+1, bag_size-1, min(min_d_cost, cost_d[i])),
recurce(i+1, bag_size, min_d_cost)
)
DP[(i, bag_size, min_d_cost)] = k
return k
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
cost = list(map(int, input().split()))
cost_d = list(map(int, input().split()))
DP = {}
print(recurce(0, m, min_d))
Time complexity: O(m * n)
Space Complexity: O(m * n * n)
2. Heap:
Solution author: nihal_47
The idea of this solution is to first sort the data based on delivery costs, Pickup m-1
items with the highest prices using a heap. And then select one item based on delivery cost + price
that maximizes the total cost.
SOLUTIONS
import heapq
t = int(input())
for _ in range(t):
n, m = map(int, input().split())
li = list(map(int, input().split()))
data = []
temp = list(map(int, input().split()))
for i in range(n):
data.append([temp[i], li[i]])
data.sort(key=lambda x: x[0])
ans = 0
psum = [0] * (n+1)
pq = []
heapq.heapify(pq)
sum = 0
for i in range(n-1, 0, -1):
if (i >= (n - (m-1))):
sum += data[i][1]
psum[i] = sum
heapq.heappush(pq, data[i][1])
else:
heapq.heappush(pq, data[i][1])
sum += data[i][1]
sum -= heapq.heappop(pq)
psum[i] = sum
for i in range(n):
if (i+m-1 < n):
ans = max(ans, data[i][0] * m + (psum[i+1] + data[i][1]))
print(ans)
Time Complexity: O(n * log n)
Space Complexity: O(n)
Note: The first solution will not pass subtask 2 in the original problem but it was a good approach to know about, hence we decided to include that in the editorial.
Feel free to share other approaches.