캠퍼스를 나타내는 2D 그리드가 있고 N명의 작업자와 M개의 자전거가 있다고 가정합니다. 값은 N <=M입니다. 이제 각 작업자와 자전거는 이 그리드에서 2D 좌표에 있습니다. 따라서 각 작업자에게 하나의 고유한 자전거를 할당하여 각 작업자와 할당된 자전거 간의 맨해튼 거리의 합이 최소가 되도록 하려는 경우입니다.
두 점 p1과 p2 사이의 맨해튼 거리는 (p1, p2) =|p1.x - p2.x| + |p1.y - p2.y|. 우리는 각 작업자와 할당된 자전거 사이의 맨해튼 거리의 가능한 최소 합을 찾아야 합니다.
따라서 입력이 작업자 =[[0,0],[2,1]]인 경우 자전거 =[[1,2],[3,3]]
그러면 출력은 6
이 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
함수 도우미()를 정의합니다. 시간이 걸립니다,b
-
반환 |a[0]-b[0]| + |a[1] - b[1]|
-
-
함수 solve()를 정의합니다. 이것은 bikes,workers,bikev,i:=0이 필요합니다.
-
info :=i와 bikev가 있는 목록
-
메모에 정보가 있는 경우
-
회신 메모[정보]
-
-
i가 작업자의 크기와 같으면
-
0 반환
-
-
temp :=무한대
-
범위 0에서 자전거 크기까지의 j에 대해
-
bikev[j]가 0이 아니면
-
바이크[j]:=1
-
temp :=최소 온도, helper(workers[i], bikes[j]) +solve(bikes, workers, bikev, i+1)
-
바이크[j]:=0
-
-
-
메모[정보]:=임시
-
반환 온도
-
assignBikes() 함수를 정의합니다. 작업자, 자전거가 필요합니다.
-
bikev :=크기가 자전거 크기와 같은 목록, false로 채우십시오.
-
메모:=새 지도
-
반환 해결(자전거, 작업자, 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