数据结构
网络
关系型数据库管理系统 (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 次查看
