Algoritmo codicioso - Argumento de intercambio

Question

Considere el siguiente problema :

Entrada: $2n$ números enteros positivos (se permiten repeticiones) $l_1,l_2, ..., l_{2n}$ .

La salida: $n$ pares $(l_{11}, l_{12}), (l_{21}, l_{22}), ..., (l_{n1}, l_{n2})$ tal que $\sum_{j=1}^{n} l_{j1}\cdot l_{j2}$ es máxima.

Mi solución es elegir los 2 enteros más grandes de la entrada en cada iteración codiciosa, y proporcionará la suma máxima ( $\sum_{j=1}^{n} l_{j1}\cdot l_{j2}$ ).

Estoy tratando de probar la corrección del algoritmo utilizando el argumento de intercambio por inducción, pero no estoy seguro de cómo demostrar formalmente que después de intercambiar un elemento entre mi solución y la solución óptima, tengo una solución que no es peor que antes.

Agradeceré cualquier indicación.

Gracias.

Answer 1

Aquí tienes una forma de ver que tu solución es máxima (aunque no necesariamente máxima, para eso mira los comentarios de esta respuesta):

Dejemos que $a\geq b\geq c\geq d$ .

Entonces tenemos que $$(ab+cd)-(ac+bd)=a(b-c)+d(c-b)=(a-d)(b-c)\geq 0$$ con igualdad si $b=c$ o $a=d$ . Sin embargo, en cualquiera de los dos casos el "canje" sólo intercambia números iguales. Del mismo modo, tenemos que $$(ab+cd)-(ad+bc)=a(b-d)+c(d-b)=(a-c)(b-d)\geq 0$$ con igualdad si $a=c$ o $b=d$ . Sin embargo, en cualquiera de los casos el "canje" sólo intercambia números iguales.