Python 中的校园自行车 II

pythonserver side programmingprogramming

假设我们有一个 2D 网格，代表一个校园，有 N 名工人和 M 辆自行车，N 的值 <= M。现在每个工人和自行车都位于此网格上的 2D 坐标中。因此，如果我们想为每个工人分配一辆唯一的自行车，以便每个工人和他们分配的自行车之间的曼哈顿距离总和最小。

我们知道两个点 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 的列表
如果 info 存在于 memo 中，则
- 返回 memo[info]
如果 i 与 worker 的大小相同，则
- 返回 0
temp := infinity
对于 j 在 0 到 bikes 的大小范围内，执行
- 如果 bikev[j] 非零，则
  - bikev[j]:= 1
  - temp := minimum of temp, helper(workers[i], bikes[j]) +solve(bikes, worker, bikev, i+1)
  - bikev[j]:= 0
memo[info]:= temp
return temp
定义一个函数assignBikes()。这将需要工人、自行车
bikev := 一个大小与自行车大小相同的列表，用 false 填充
memo:= 一张新地图
return resolve(bikes, worker, 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]]))