สมมติว่าเรามีตาราง 2 มิติ ซึ่งแสดงถึงวิทยาเขต มีคนงาน N และจักรยาน M ค่าของ N <=M ตอนนี้ พนักงานและจักรยานแต่ละคนอยู่ในพิกัด 2 มิติบนตารางนี้ ดังนั้น หากเราต้องการกำหนดจักรยานที่ไม่ซ้ำกันหนึ่งคันให้กับพนักงานแต่ละคน เพื่อให้ระยะทางรวมของแมนฮัตตันระหว่างพนักงานแต่ละคนกับจักรยานที่มอบหมายนั้นมีค่าน้อยที่สุด
เรารู้ว่าระยะห่างของแมนฮัตตันระหว่างจุดสองจุด p1 และ p2 คือ (p1, p2) =|p1.x - p2.x| + |p1.y - p2.y|. เราต้องหาผลรวมขั้นต่ำของระยะทางแมนฮัตตันระหว่างพนักงานแต่ละคนกับจักรยานที่มอบหมาย
ดังนั้น ถ้าข้อมูลเข้าเหมือนคนทำงาน =[[0,0],[2,1]], bikes =[[1,2],[3,3]]
แล้วผลลัพธ์จะเป็น 6
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชั่น helper() นี่จะใช้เวลา a,b
-
กลับ |a[0]-b[0]| + |a[1] - b[1]|
-
-
กำหนดฟังก์ชัน Solve() นี้จะใช้เวลา bikes, คนงาน,bikev,i:=0
-
info :=รายการที่มี i และ bikev
-
หากมีข้อมูลอยู่ในบันทึกช่วยจำ
-
บันทึกการส่งคืน[ข้อมูล]
-
-
ถ้าฉันมีขนาดเท่ากับคนงานแล้ว
-
คืนค่า 0
-
-
อุณหภูมิ :=อินฟินิตี้
-
สำหรับ j ในช่วง 0 ถึงขนาดของจักรยาน ให้ทำ
-
ถ้าไม่ใช่ bikev[j] ก็ไม่ใช่ศูนย์ แล้ว
-
bikev[j]:=1
-
temp :=ขั้นต่ำของ temp, helper(workers[i], bikes[j]) +solve(bikes, workers, bikev, i+1)
-
bikev[j]:=0
-
-
-
บันทึก[info]:=ชั่วคราว
-
อุณหภูมิกลับ
-
กำหนดฟังก์ชัน assignBikes() งานนี้ต้องใช้คนทำงาน จักรยาน
-
bikev :=รายการที่มีขนาดเท่ากับขนาดของจักรยาน กรอกเป็นเท็จ
-
บันทึก:=แผนที่ใหม่
-
ผลตอบแทนการแก้ (จักรยาน, คนงาน, 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
