There are n cities [1, 2, 3, .... n] and k available hospitals. k < n. We need to place hospitals into the cities. How to place these hospitals to minimize the average distance from each cities to the closest hospitals.?
Right now my thought is using dynamic programming with a 2D array of size n * k. Then I know optimal solution will be f(n, k) = , which pump𝑘 is the position at the median of cities 𝑖+1,...,𝑛. I believe this is the right approach but I do not know how to store the location of each hospitals. Please help