Câu hỏi thực tế diễn ra như sau:Giảm thiểu tổng khoảng cách: Vấn đề tối ưu hóa
McDonald's đang có kế hoạch mở một số khớp (n) dọc theo đường cao tốc thẳng. Các khớp này yêu cầu kho chứa thực phẩm của chúng. Một nhà kho có thể lưu trữ thực phẩm cho bất kỳ số lượng khớp, nhưng phải được đặt tại một trong các khớp. McD có một số lượng hạn chế kho (nói k) có sẵn, và muốn đặt chúng theo cách sao cho khoảng cách trung bình của các khớp từ kho gần nhất của chúng được giảm thiểu.
Cho một mảng (n phần tử) của tọa độ của các khớp và số nguyên 'k', trả về một mảng các phần tử 'k' cho tọa độ vị trí tối ưu của kho.
Rất tiếc, tôi không có sẵn bất kỳ ví dụ nào kể từ khi tôi viết xuống từ bộ nhớ. Dù sao, một mẫu có thể là:
array = {1,3,4,5,7,7,8,10,11} (n = 9)
k = 1
Ans: {7 }
Đây là những gì tôi đã suy nghĩ: Đối với k = 1, chúng ta chỉ cần tìm ra vị trí trung bình của tập hợp, sẽ cho vị trí tối ưu của nhà kho. Tuy nhiên, đối với k> 1, tập hợp đã cho nên được chia thành các tập con 'k' (phân tách, và các phần tử tiếp giáp của siêu bên), và trung bình cho mỗi tập con sẽ cung cấp cho các vị trí kho. Tuy nhiên, tôi không hiểu về cơ sở nào các tập con 'k' nên được hình thành. Cảm ơn trước.
EDIT: Có một biến thể cho vấn đề này: Thay vì tổng hợp/avg, hãy giảm thiểu khoảng cách tối đa giữa doanh nghiệp và nhà kho gần nhất. Tôi cũng không nhận được điều này.
Đây có phải là bài tập về nhà không? Nếu có, hãy gắn thẻ như vậy. –
Điều này đã đến trong một cuộc thi. –
@ArpitTarang Tôi gặp phải vấn đề tương tự. Bạn có thể giải quyết nó không? – user3634974