N números, pares N / 2.Minimizando la suma máxima de un emparejamiento.Demostrando algoritmo codicioso

Question

así que diga que tengo n números, donde n es incluso. Quiero combinar los números de manera que se minimiza la suma máxima de los pares. Por ejemplo, -2, 3, 4, 5. La pareja ideal es (-2, 5), (3, 4), ya que su suma máxima es 3 + 4= 7, y esa es la suma mínima posible para una suma máxima en cualquier pareja. La clave para el algoritmo es ordenar los valores de lo menos a mayor. Luego empareje lo menos con el más grande, y así sucesivamente, hasta que llegue al centro del pedido.

Ejemplo: 3, -2, 4, 5

algoritmo ordena los valores: -2, 3, 4, 5

luego pares primero con el último: (-2, 5)

Luego, pare el siguiente primero y último: (3, 4)

termina ya que no quedan parejas.

Este es un algoritmo codicioso y estoy tratando de probar que siempre es correcto usar un enfoque de "estancias codicianas por delante". Mi problema es que estoy luchando para demostrar que la suma máxima del algoritmo siempre es siempre $ \ leq $ suma máxima óptima. Mi intención debía suponer por contradicción de que la suma máxima óptima es $ <$ la suma máxima del algoritmo. Pero no estoy seguro de cómo encontrar una contradicción. ¿Cómo va a ir esta prueba?

Answer 1

¿Puede ver por qué $ \ max ((- 2) +5, 3 + 4) \ lt \ max (-2 + 3, 4 + 5) $ ?

La razón es simple. Debido a la derecha, el número 5 máximo no está emparejado con el número mínimo.

---

Deje que los números sean $ a_1 \ le a_2 \ le \ cdots \ le a_n $ . Deja que los números sean emparejados de alguna manera.

• Si $ a_n $ está emparejado con $ A_1 $ , estamos hechos en este redondo.

• Supongamos $ a_n $ se empareja con $ a_j $ , $ j \ NO= 1 $ . Luego, $ A_1 $ se combina con $ a_k $ para algunos $ k \ no= n $ . Así que tenemos dos pares, $ \ {A_N, A_J \ \} $ y $ \ {A_1, A_K \} $ < / span>. Las sumas de estos dos pares son $ A_N + A_J $ y $ A_1 + A_K $ , el grande de los cuales es $ A_N + A_J $ .

  Permítanos cambiar $ a_j $ y $ A_1 $ para que $ a_n $ se emparejará con $ A_1 $ y $ A_J $ Par con $ A_K $ . Las sumas de los dos nuevos pares son $ A_N + A_1 $ y $ a_j + a_k $ , ambos de que está en la mayoría de $ a_n + a_j $ , es decir, el grande de ellos está en la mayoría $ a_n + a_j $ < / span>. Entonces, después del interruptor, la suma máxima de los pares que involucra $ A_N, A_J, A_K, A_1 $ no aumenta. Dado que otros pares se mantienen iguales, por lo que después del interruptor, la suma máxima de todos los pares no aumenta.

Continuando con este proceso, nos aseguraremos de que el número más grande restante esté emparejado con el número más pequeño que quede en cada ronda. La suma máxima de los pares nunca aumentará en cada ronda. Después de $ n / 2 $ rondas, llegaremos al emparejamiento donde $ A_K $ está emparejado con $ a_ {n + 1-k} $ .

Puede ver que el enfoque anterior es, de hecho, el enfoque "codicioso que permanece por delante".