โปรแกรมค้นหาระยะทางรวมขั้นต่ำระหว่างบ้านและกล่องจดหมายที่ใกล้ที่สุดใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่าบ้านและมีค่าอื่น k ที่นี่ บ้าน[i] หมายถึงที่ตั้งของบ้านเลขที่ริมถนน เราต้องจัดสรร k กล่องจดหมายบนถนน และหาระยะทางรวมขั้นต่ำระหว่างบ้านแต่ละหลังกับกล่องจดหมายที่ใกล้ที่สุด

ดังนั้น ถ้าอินพุตเหมือนบ้าน =[6,7,9,16,22] k =2 แล้วเอาต์พุตจะเป็น 9 เพราะถ้าเราวางเมลบ็อกซ์ที่ 7 และ 18 ระยะทางรวมขั้นต่ำจากแต่ละบ้านคือ |6 -7|+|7-7|+|9-7|+|16- 18|+|22-18| =1+0+2+2+4 =9.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เรียงรายชื่อบ้าน

• กำหนดฟังก์ชัน util() นี่จะใช้เวลา idx, n, k

• ถ้า k เท่ากับ 1 แล้ว

  • core :=houses[quotient of (n + idx)/2]

  • ส่งคืนผลรวมขององค์ประกอบทั้งหมดของ [|houses[i] - core| สำหรับแต่ละ i ในช่วง idx ถึง n])

• ผลลัพธ์ :=อนันต์

• สำหรับฉันอยู่ในช่วง idx ถึง n ทำ

  • ถ้า n - i

    • ออกจากวง

  • ผลลัพธ์ :=ผลลัพธ์ขั้นต่ำและ util(idx, i, 1) + util(i+1, n, k - 1)

• ส่งคืนผลลัพธ์

• จากวิธีหลัก ให้ทำดังนี้:

• ผลตอบแทนการใช้(0, ขนาดบ้าน - 1, k)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

def solve(houses, k):
   houses.sort()
   def util(idx, n, k):
      if k == 1:
         core = houses[(n + idx) // 2]
         return sum([abs(houses[i] - core) for i in range(idx, n + 1)])
      result = float('inf')
      for i in range(idx, n + 1):
         if n - i < k - 1:
            break
         result = min(result, util(idx, i, 1) + util(i+1, n, k - 1))
      return result
   return util(0, len(houses) - 1, k)

houses = [6,7,9,16,22]
k = 2
print(solve(houses, k))

อินพุต

[6,7,9,16,22], 2

ผลลัพธ์

9