N chiffres, n / 2 paires.Minimiser la somme maximale d'un couplage.Prouver algorithme gourmand

Question

Ainsi dire que j'ai des chiffres, où n est même. Je veux associer les chiffres de sorte que la somme maximale des paires est minimisée. Par exemple -2, 3, 4, 5. Le jumelage idéal est (-2, 5), (3, 4), car sa somme maximale est de 3 + 4= 7, et c'est la somme minimale possible pour une somme maximale dans n'importe quel couplage. La clé de l'algorithme est de trier les valeurs du moins au plus grand. Ensuite, associez le moins avec le plus grand, et ainsi de suite, jusqu'à ce que vous atteigniez le centre de la commande.

Exemple: 3, -2, 4, 5

algorithme trie les valeurs: -2, 3, 4, 5

Puis les paires d'abord avec la dernière: (-2, 5)

Ensuite, les paires suivantes sont disponibles en premier et dernier: (3, 4)

se termine depuis aucune paire.

Il s'agit d'un algorithme gourmand et j'essaie de prouver qu'il est toujours correct en utilisant une approche "séjours gourmands à venir". Mon problème est que je me lance de montrer que la somme maximale de l'algorithme est toujours $ \ Leq $ somme maximale optimale. Mon intention était de supposer une contradiction que la somme maximale optimale est $ la somme maximale de l'algorithme. Mais je ne suis pas sûr de savoir comment trouver une contradiction. Comment cette preuve irait-elle?

Answer 1

Pouvez-vous voir pourquoi $ \ max (((2) +5, 3 + 4) \ lt \ max (-2 + 3, 4 + 5) $ ?

La raison est simple. Parce que sur le côté droit, le nombre maximum 5 n'est pas jumelé avec le nombre minimum.

---

laissez les chiffres sont $ a_1 \ le a_2 \ le \ CDOT \ Le a_n $ . Laissez les chiffres être jumelés d'une manière ou d'une autre.

• si $ a_n $ est jumelé avec $ A_1 $ , nous sommes terminés à cette rond.

• suppose $ a_n $ est jumelé avec $ a_j $ , $ J \ non= 1 $ . Alors $ a_1 $ est associé à $ a_k $ pour certains $ k \ non= n $ . Nous avons donc deux paires, $ \ {a_n, a_j \} $ et $ \ {a_1, a_k \} $ < / span>. Les sommes de ces deux paires sont $ a_n + a_j $ et $ a_1 + a_k $ , le grand dont est $ a_n + a_j $ $ .

  laissez-vous passer $ a_j $ et $ a_1 $ donc que $ a_n $ va paire avec $ a_1 $ et $ a_j $ Paire avec $ A_K $ . Les sommes des deux nouvelles paires sont $ a_n + a_1 $ et $ a_j + a_k $ , tous les deux qui est au plus $ a_n + a_j $ , c'est-à-dire que le grand d'entre eux est au plus $ a_n + a_j $ < / span>. Donc, après l'interrupteur, la somme maximale des paires impliquant $ a_n, a_j, a_k, a_1 $ n'augmente pas. Étant donné que d'autres couples restent le même, alors après l'interrupteur, la somme maximale de toutes les paires n'augmente pas.

Continuer ce processus, nous veillerons à ce que le plus grand nombre restant soit associé au plus petit nombre restant à chaque tour. La somme maximale des paires n'augmentera jamais chaque tour. Après $ N / 2 $ tours, nous atteindrons l'appariement où $ a_k $ est jumelé avec $ a_ {n + 1-k} $ .

Vous pouvez voir que l'approche ci-dessus est en effet la approche "Greedy Séjours à venir".