Campus Bikes II trong Python

Cho một lưới 2D đại diện cho khuôn viên trường, có N công nhân và M chiếc xe đạp (N <= M). Mỗi công nhân và xe đạp nằm ở một tọa độ 2D trên lưới này. Cần gán một chiếc xe đạp duy nhất cho mỗi công nhân sao cho tổng khoảng cách Manhattan giữa mỗi công nhân và xe đạp được gán là nhỏ nhất.

Khoảng cách Manhattan giữa hai điểm p1 và p2 là |p1.x - p2.x| + |p1.y - p2.y|. Tìm tổng khoảng cách Manhattan tối thiểu.

Ví dụ, với workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]], đầu ra là 6.

Giải pháp sử dụng quy hoạch động với bitmask (memoization):

• Hàm helper(a, b) tính khoảng cách Manhattan.
• Hàm solve(bikes, workers, bikev, i) đệ quy với memoization:
  • bikev là mảng đánh dấu xe đạp đã dùng.
  • Thử gán từng xe đạp chưa dùng cho công nhân i, cập nhật kết quả tối thiểu.
• Hàm assignBikes khởi tạo và gọi solve.

Ví dụ triển khai

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, bikev, i+1))
                bikev[j] = 0
        self.memo[info] = temp
        return temp
    
    def assignBikes(self, workers, bikes):
        bikev = [False for _ 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]]

Đầu ra

6