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

ปัญหา

มีอาร์เรย์ houses แทนตำแหน่งบ้าน และ k กล่องจดหมาย หาตำแหน่งวางกล่องจดหมาย k ตัว ให้ผลรวมระยะทางจากแต่ละบ้านถึงกล่องจดหมายที่ใกล้ที่สุดน้อยที่สุด

ตัวอย่าง

houses = [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)

ขั้นตอนการแก้ปัญหา

1. เรียง houses
2. ฟังก์ชัน util(idx, n, k):
   • ถ้า k == 1: core := houses[(n+idx)//2], คืน sum(|houses[i] - core| for i in idx..n)
   • result := inf
   • วน i จาก idx ถึง n:
     • ถ้า n - i < k - 1: break
     • result := min(result, util(idx, i, 1) + util(i+1, n, k-1))
   • คืน result
3. คืน util(0, len(houses)-1, k)

การนำไปใช้งาน (Python)

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