找出购买所有物品的最低花费 Python 程序

假设我们有N件物品，这些物品分别标记为0、1、2、…、N-1。然后，我们得到一个大小为S的2D列表称为sets。在这里，我们可以购买第i个集合以价格sets[i,2]，并接收从sets[i,0]到sets[i,1]之间的所有物品。此外，我们有一个大小为N的列表称为removals，我们可以以价格removals[i]抛弃第i个元素的1个实例。因此，我们必须找到购买从0到N-1的每个元素的精确一个的最低成本，如果这不能做到则结果为-1。

因此，如果输入如下 sets = [
   [0, 4, 4],
   [0, 5, 12],
   [2, 6, 9],
   [4, 8, 10]
]

removals = [2, 5, 4, 6, 8]，那么输出将是4。

要解决此问题，我们需要按照以下步骤进行操作 −

• N := removals的大小

• 图 := 大小为(N+1)x(N+1)的新矩阵

• 对于每一个被称为s, e, w的集合，做一下操作：

  • 将[e+1, w]加入到图[s]中
• 对于removals中的索引i和项目r中的项i, r，执行以下操作
  • 将[i, r]添加到图[i + 1]中
• pq := 新堆

• dist := 新地图

• dist[0] := 0

• 当pq不为空的时候，执行以下操作

  • d, e := 从堆pq中移除最小项

  • 如果dist[e] < d是非零的，则执行下一次迭代

  • 如果e与N相同，则执行以下操作

    • 返回 d
  • 对于图[e]中的每个nei，w而言，执行以下操作
    • d2 := d + w

    • 如果d2 < dist[nei]是非零的，则执行以下操作

    • dist[nei] := d2

    • [d2，nei]加入pq

• 返回 -1

示例

让我们看下面的示例来更好地理解 −

import heapq
from collections import defaultdict
class Solution:
   def solve(self, sets, removals):
      N = len(removals)
      graph = [[] for _ in range(N + 1)]
      for s, e, w in sets:
         graph[s].append([e + 1, w])
      for i, r in enumerate(removals):
         graph[i + 1].append([i, r])
      pq = [[0, 0]]
      dist = defaultdict(lambda: float("inf"))
      dist[0] = 0
      while pq:
         d, e = heapq.heappop(pq)
         if dist[e] < d:
            continue
         if e == N:
            return d
         for nei, w in graph[e]:
            d2 = d + w
            if d2 < dist[nei]:
               dist[nei] = d2
               heapq.heappush(pq, [d2, nei])
      return -1

ob = Solution()
print (ob.solve([
   [0, 4, 4],
   [0, 5, 12],
   [2, 6, 9],
   [4, 8, 10]
], [2, 5, 4, 6, 8]))

输入

[[0, 4, 4],
[0, 5, 12],
[2, 6, 9],
[4, 8, 10]], [2, 5, 4, 6, 8]

输出

4