La pregunta real es la siguiente:Minimización de la suma de distancias: problema de optimización
McDonald's tiene previsto abrir una serie de juntas (digamos n) a lo largo de una carretera recta. Estas juntas requieren almacenes para almacenar sus alimentos. Un almacén puede almacenar alimentos para cualquier cantidad de juntas, pero tiene que ubicarse en una de las juntas solamente. McD tiene un número limitado de almacenes (por ejemplo, k) disponibles, y desea ubicarlos de manera que se minimice la distancia promedio de las juntas desde su almacén más cercano.
Dada una matriz (n elementos) de coordenadas de las uniones y un número entero 'k', devuelve una matriz de 'k' elementos que proporcionan las coordenadas del posicionamiento óptimo de los almacenes.
Lo siento, no tengo ningún ejemplo disponible ya que estoy escribiendo esto de memoria. De todos modos, una muestra podría ser:
array = {1,3,4,5,7,7,8,10,11} (n = 9)
k = 1
Ans: {7 }
Esto es lo que he estado pensando: Para k = 1, podemos simplemente averiguar la mediana del conjunto, que daría la ubicación óptima del almacén. Sin embargo, para k> 1, el conjunto dado se debe dividir en subconjuntos 'k' (disjuntos y elementos contiguos del superconjunto), y la mediana para cada subconjunto daría las ubicaciones del almacén. Sin embargo, no entiendo en qué se basan los subconjuntos 'k'. Gracias por adelantado.
EDITAR: También hay una variación de este problema: en lugar de sum/avg, minimice la distancia máxima entre una junta y su almacén más cercano. Tampoco entiendo esto ...
¿Es esto una tarea? Si es así, márquelo como tal, por favor. –
Bueno, esto vino en una competencia. –
@ArpitTarang Me encontré con el mismo problema. ¿Pudiste resolverlo? – user3634974