資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：找出購買所有物品的最低成本
假設我們有N個物品，標記為0、1、2、…、N-1。然後，我們得到一個大小為S的二維列表sets。我們可以以sets[i,2]的價格購買第i個集合，並獲得sets[i, 0]到sets[i, 1]之間的所有物品。此外，我們還有一個大小為N的列表removals，其中我們可以以removals[i]的價格丟棄第i個元素的一個例項。因此，我們必須找出精確購買從0到N-1（包含）每個元素的一個例項的最低成本，或者如果無法完成則結果為-1。
So, if the input is like sets = [ [0, 4, 4], [0, 5, 12], [2, 6, 9], [4, 8, 10] ]
removals = [2, 5, 4, 6, 8]，則輸出將為4。
為了解決這個問題，我們將遵循以下步驟：
N := removals的大小
graph := 一個大小為(N + 1) x (N + 1)的新矩陣
對於每個s、e、w in sets，執行以下操作：
將[e+1, w]新增到graph[s]
對於每個索引i和物品r in removals，執行以下操作：
將[i, r]新增到graph[i + 1]
pq := 一個新的堆
dist := 一個新的對映
dist[0] := 0
當pq不為空時，執行以下操作：
d, e := 從堆pq中移除最小的項
如果dist[e] < d不為零，則：
繼續下一次迭代
如果e與N相同，則：
返回d
對於每個nei, w in graph[e]，執行以下操作：
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
更新於: 2020-12-23
277 次瀏覽
廣告