資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python 實現校園腳踏車分配 II
假設我們有一個二維網格，表示一個校園，有 N 個工人和 M 輛腳踏車，其中 N <= M。現在每個工人和腳踏車都在此網格上的二維座標上。所以，如果我們想為每個工人分配一輛唯一的腳踏車，使得每個工人與其分配的腳踏車之間的曼哈頓距離之和最小。
我們知道，兩點 p1 和 p2 之間的曼哈頓距離為 (p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|。我們必須找到每個工人與其分配的腳踏車之間的曼哈頓距離之和的最小可能值。
所以，如果輸入類似於 workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
那麼輸出將為 6
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 helper()。它將接收 a 和 b 作為輸入。
返回 |a[0]-b[0]| + |a[1] - b[1]|
定義一個函式 solve()。它將接收 bikes、workers、bikev 和 i（初始值為 0）作為輸入。
info := 一個包含 i 和 bikev 的列表
如果 memo 中存在 info，則
返回 memo[info]
如果 i 等於 workers 的大小，則
返回 0
temp := 無窮大
對於從 0 到 bikes 大小的範圍內的 j，執行以下操作：
如果 bikev[j] 不為零，則
bikev[j]:= 1
temp := temp、helper(workers[i], bikes[j]) + solve(bikes, workers, bikev, i+1) 的最小值
bikev[j]:= 0
memo[info]:= temp
返回 temp
定義一個函式 assignBikes()。它將接收 workers 和 bikes 作為輸入。
bikev := 一個大小與 bikes 大小相同的列表，用 false 填充它
memo:= 一個新的對映
返回 solve(bikes, workers, bikev)
示例
讓我們看看下面的實現，以便更好地理解：
class Solution(object):
def helper(self,a,b):
return abs( (a[0]-b[0]) ) + abs( (a[1] - b[1]) )
def solve(self,bikes,workers,bikev,i=0):
info = (i,tuple(bikev))
if info in self.memo:
return self.memo[info]
if i == len(workers):
return 0
temp = float('inf')
for j in range(len(bikes)):
if not bikev[j]:
bikev[j]=1
temp = min(temp,self.helper(workers[i],bikes[j])+self.solve(bikes,workers,bi
kev,i+1))
bikev[j]=0
self.memo[info]= temp
return temp
def assignBikes(self, workers, bikes):
bikev = [False for i in range(len(bikes))]
self.memo={}
return self.solve(bikes,workers,bikev)
ob = Solution()
print(ob.assignBikes([[0,0],[2,1]],[[1,2],[3,3]]))輸入
[[0,0],[2,1]] [[1,2],[3,3]]
輸出
6
199 次檢視
