Campus Bikes II: กำหนดจักรยานให้พนักงานเพื่อระยะทางรวมน้อยที่สุดใน Python

มีกริด 2 มิติแทนحرมมหาวิทยาลัย มีพนักงาน N คน และจักรยาน M คัน (N ≤ M) แต่ละคนและจักรยานอยู่ที่พิกัด 2 มิติ ต้องจับคู่จักรยานให้แต่ละพนักงาน 1 คัน โดยไม่ซ้ำกัน เพื่อให้ผลรวมระยะทางแมนฮัตตันน้อยที่สุด

ระยะทางแมนฮัตตันระหว่างจุด p1 และ p2 คือ |p1.x - p2.x| + |p1.y - p2.y|

ตัวอย่าง: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]] ผลลัพธ์ = 6

แนวทางแก้ปัญหา (Backtracking + Memoization)

1. ฟังก์ชัน helper(a, b) คำนวณระยะทางแมนฮัตตัน
2. ฟังก์ชัน solve(bikes, workers, bikev, i) ใช้ backtracking พร้อม memoization:
   • bikev = รายการบูลลีนบอกว่าจักรยานคันไหนถูกใช้แล้ว
   • ลองจับคู่พนักงานคนที่ i กับจักรยานทุกคันที่ว่าง
   • เก็บค่าต่ำสุดใน memo ด้วย key (i, tuple(bikev))
3. ฟังก์ชัน assignBikes เริ่มต้นการคำนวณ

ตัวอย่างโค้ด

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]]))  # Output: 6

อินพุต

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

เอาต์พุต

6