Campus Bikes II bằng Python

Giả sử chúng ta có một lưới 2D, đại diện cho một khuôn viên, có N công nhân và M xe đạp, Giá trị của N <=M. Bây giờ Mỗi công nhân và xe đạp ở một tọa độ 2D trên lưới này. Vì vậy, nếu chúng tôi muốn chỉ định một chiếc xe đạp duy nhất cho mỗi công nhân để tổng khoảng cách Manhattan giữa mỗi công nhân và chiếc xe đạp được giao của họ là nhỏ nhất.

Ta biết rằng khoảng cách Manhattan giữa hai điểm p1 và p2 là (p1, p2) =| p1.x - p2.x | + | p1.y - p2.y |. Chúng tôi phải tìm tổng khoảng cách Manhattan tối thiểu có thể có giữa mỗi công nhân và chiếc xe đạp được giao của họ.

Vì vậy, nếu đầu vào giống như worker =[[0,0], [2,1]], bikes =[[1,2], [3,3]]

thì đầu ra sẽ là 6

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Định nghĩa một hàm trợ giúp (). Điều này sẽ mất a, b
- trả về | a [0] -b [0] | + | a [1] - b [1] |
Định nghĩa một hàm giải quyết (). Điều này sẽ mất xe đạp, công nhân, bikev, i:=0
info:=một danh sách có tôi và bikev
nếu thông tin có trong bản ghi nhớ thì
- trả lại thư báo [thông tin]
nếu tôi bằng cỡ công nhân thì
- trả về 0
temp:=infinity
đối với j trong phạm vi từ 0 đến kích thước của xe đạp, thực hiện
- nếu không bikev [j] khác 0 thì
  - bikev [j]:=1
  - temp:=tối thiểu của nhiệt độ, người trợ giúp (công nhân [i], xe đạp [j]) + giải quyết (xe đạp, công nhân, xe đạp, i + 1)
  - bikev [j]:=0
bản ghi nhớ [thông tin]:=temp
trở lại nhiệt độ
Định nghĩa một hàm gánBikes (). Điều này sẽ đưa công nhân, xe đạp
bikev:=một danh sách có kích thước bằng với kích thước của xe đạp, điền vào giá trị này bằng false
memo:=a new map
return giải quyết (xe đạp, công nhân, xe đạp)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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

Đầu vào

[[0,0],[2,1]] [[1,2],[3,3]]

Campus Bikes II bằng Python

Ví dụ

Đầu vào

Đầu ra