¿Cómo un par [matemáticas] n [/ matemáticas] personas con ingresos variables de la mejor manera?

Answer 1

Primero, veamos que en el mejor emparejamiento, [math] i_1 [/ math] y [math] i_2 [/ math] se emparejarán juntos (suponiendo que estos estén ordenados previamente para que [math] i_1 [/ math] y [ matemáticas] i_2 [/ matemáticas] son ​​los dos ingresos más pequeños). Supongamos que, en cambio, [math] i_1 [/ math] está emparejado con [math] i_j [/ math] y [math] i_2 [/ math] con [math] i_k [/ math]. Ahora consideremos [matemáticas] | i_j – i_1 | + | i_k – i_2 | [/ matemáticas]. Esto es igual a [math] i_j + i_k – i_1 – i_2 [/ math]. Tenga en cuenta que no importa cuál de [math] i_j, i_k [/ math] es mayor para esta suma, por lo que asumiremos [math] i_k \ ge i_j [/ math]. Entonces tenemos [matemáticas] i_1 \ le i_2 \ le i_j \ le i_k [/ matemáticas], dándonos [matemáticas] | i_j – i_1 | = | i_j – i_2 | + | i_2 – i_1 | [/ matemáticas] y [matemáticas] | i_k – i_2 | = | i_k – i_j | + | i_j – i_2 | [/ matemáticas]. Al unirlos, tenemos [matemáticas] | i_j – i_1 | + | i_k – i_2 | = | i_j – i_2 | + | i_2 – i_1 | + | i_k – i_j | + | i_j – i_2 | \ ge | i_2 – i_1 | + | i_k – i_j | [/ matemáticas]. Por lo tanto, solo podemos reducir la suma de las disparidades emparejando [math] i_1 [/ math] con [math] i_2 [/ math] y [math] i_j [/ math] con [math] i_k [/ math]. Por lo tanto, existe un emparejamiento óptimo en el que las personas con los dos ingresos más pequeños están emparejadas.

Esto nos da el algoritmo. Emparejamos los dos ingresos más pequeños, luego procedemos recursivamente con el resto, emparejando los siguientes dos más pequeños y así sucesivamente.

Actualización : Si se permite un número impar de personas y queremos emparejar a la mayor cantidad de personas posible mientras minimizamos la suma, podemos calcular todas las soluciones parciales para las [matemáticas] 2k [/ matemáticas] más ricas y [matemáticas] 2k [/ matemática] personas más pobres para cada [matemática] k <n / 2 [/ matemática]. Estos pueden calcularse en tiempo lineal, como se describió anteriormente. Luego encuentre a la persona para quien se minimiza la suma de la solución para las personas más ricas y pobres. Tenga en cuenta que debe haber un número par de personas más ricas y pobres en una solución óptima, ya que de lo contrario estamos haciendo coincidir a alguien más rico que la persona que estamos dejando con alguien más pobre que la persona que estamos dejando de lado, y podríamos hacer una mejor solución al hacer coincidir uno de ellos con la persona que estamos dejando de lado.

Answer 2

Puede configurar esto como un problema de coincidencia ponderada máxima en un gráfico completo estableciendo el peso del borde [math] (a, b) [/ math] en [math] – | i_a – i_b | [/ math]. Entonces puedes usar algoritmos estándar para resolverlo.

Answer 3

Bueno, supongamos que tiene 10 ingresos que van desde 1 a 10 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

parece que el mejor arreglo sería emparejar los dos ingresos más pequeños

{1, 2} luego los siguientes 2 más pequeños

{3, 4} y así sucesivamente

{5, 6}

{7, 8}

{9, 10}

Sumar estas diferencias debería darte un 5 en este caso.

El problema que tengo con esto es que no puedo encontrar una prueba formal de esto, ni puedo encontrar un contraejemplo para refutarlo. Realmente estaría satisfecho con una refutación. Al menos sería un paso adelante.

Mi esperanza es que tal vez esto empuje a alguien con más experiencia hacia adelante.