Chương trình tìm tổng khoảng cách tối thiểu giữa nhà và bưu hộ gần nhất trong Python

Cho mảng houses (vị trí các nhà) và số k bưu hộ. Cần đặt k bưu hộ để tối thiểu hóa tổng khoảng cách từ mỗi nhà đến bưu hộ gần nhất.

Ví dụ: houses = [6,7,9,16,22], k=2 → 9. Đặt bưu hộ tại 7 và 18: |6-7|+|7-7|+|9-7|+|16-18|+|22-18| = 1+0+2+2+4 = 9.

Giải thuật (Đệ quy + Chia để trị)

1. Sắp xếp houses.
2. Hàm util(idx, n, k): min cost cho đoạn houses[idx..n] với k bưu hộ.
   • Nếu k == 1: đặt bưu hộ tại trung vị houses[(idx+n)//2], trả về tổng khoảng cách.
   • Ngược lại: thử mọi điểm cắt i từ idx đến n, lấy min của util(idx, i, 1) + util(i+1, n, k-1).
3. Gọi util(0, len(houses)-1, k).

Ví dụ minh họa

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))

Đầu vào

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

Đầu ra

9