Giả sử chúng ta có một mảng được gọi là nhà và có một giá trị khác k. Ở đây các ngôi nhà [i] đại diện cho vị trí của ngôi nhà thứ i dọc theo một con phố, chúng ta phải phân bổ k hộp thư trên phố và tìm tổng khoảng cách tối thiểu giữa mỗi ngôi nhà và hộp thư gần nhất.
Vì vậy, nếu đầu vào là các ngôi nhà =[6,7,9,16,22] k =2, thì đầu ra sẽ là 9 vì nếu chúng ta đặt hộp thư ở vị trí 7 và 18, thì tổng khoảng cách tối thiểu từ mỗi ngôi nhà là | 6 -7 | + | 7-7 | + | 9-7 | + | 16- 18 | + | 22-18 | =1 + 0 + 2 + 2 + 4 =9.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
sắp xếp các nhà trong danh sách
-
Định nghĩa một hàm dùng (). Điều này sẽ lấy idx, n, k
-
nếu k giống với 1 thì
-
lõi:=nhà [thương số của (n + idx) / 2]
-
trả về tổng của tất cả các phần tử của [| house [i] - core | cho mỗi tôi trong phạm vi idx đến n])
-
-
kết quả:=infinity
-
đối với tôi trong phạm vi idx đến n, thực hiện
-
nếu n - i
-
đi ra từ vòng lặp
-
-
kết quả:=tối thiểu của kết quả và dùng (idx, i, 1) + dùng (i + 1, n, k - 1)
-
-
trả về kết quả
-
Từ phương thức chính, thực hiện như sau:
-
trả về sử dụng (0, kích thước nhà - 1, k)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn
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