N Zahlen, N / 2-Paare.Minimierung der maximalen Summe eines Paares.Gieriger Algorithmus nachweisen

Question

Also habe ich n Zahlen, wo n sogar ist. Ich möchte die Zahlen so passen, dass die maximale Summe der Paare minimiert wird. Beispiel -2, 3, 4, 5. Das ideale Paarung ist (-2, 5), (3, 4), da seine maximale Summe 3 + 4= 7 beträgt, und das ist die minimale Summe für eine maximale Summe in jeder Paarung. Der Schlüssel zum Algorithmus besteht darin, die Werte von mindestens bis zum größten zu sortieren. Dann koppeln Sie das am wenigsten mit dem größten, und so weiter, bis Sie das Zentrum der Bestellung erreichen.

Beispiel: 3, -2, 4, 5

Algorithmus sortiert die Werte: -2, 3, 4, 5

Paare dann zuerst mit dem letzten: (-2, 5)

passt dann das nächste verfügbare zuerst und zuletzt: (3, 4)

endet, da keine Paare übrig sind.

Dies ist ein gieriger Algorithmus, und ich versuche zu beweisen, dass es immer korrekt ist, mit einem "gierigen Aufenthalten voran" Ansatz zu verwenden. Mein Thema ist, dass ich zu zeigen möchte, dass die maximale Summe des Algorithmus immer $ \ LEQ $ optimaler maximaler Summe ist. Meine Absicht war, den Widerspruch zu vermuten, dass der optimale maximale Summe $ <$ die maximale Summe der Algorithmus ist. Aber ich bin mir nicht sicher, wie ich einen Widerspruch finden kann. Wie würde dieser Beweis gehen?

Answer 1

Kannst du sehen, warum $ \ max ((- 2) +5, 3 + 4) \ lt \ max (-2 + 3, 4 + 5) $

Der Grund ist einfach. Denn auf der rechten Seite ist die maximale Anzahl 5 nicht mit der Mindestanzahl gekoppelt.

---

Lassen Sie die Zahlen $ A_1 \ le a_2 \ le \ cdots \ le a_n $ . Lassen Sie die Zahlen in irgendeiner Weise gekoppelt sein.

• Wenn $ A_N $ mit $ A_1 $ gekoppelt ist, werden wir dabei gemacht Runde.

• Angenommen, $ A_N $ wird mit $ a_j $ , $ j \ nicht= 1 $ . Dann wird $ A_1 $ mit $ A_K $ für einigen $ k \ nicht= n $ . Wir haben also zwei Paare, $ \ {a_n, a_j \} $ und $ \ {A_1, A_K \} $ < / span>. Die Summen dieser beiden Paare sind $ A_N + A_J $ und $ A_1 + A_K $ , der große davon ist $ a_n + a_j $ .

  lasst uns wechseln $ a_j $ und $ a_1 $ , so dass $ A_N $ wird mit $ A_1 $ und $ a_j $ Paar mit $ A_K $ . Die Summen der beiden neuen Paare sind $ a_n + a_1 $ und $ a_j + a_k $ , beide Welches ist höchstens $ a_n + a_j $ , dh der große von ihnen ist höchstens $ a_n + a_j $ < / span>. Nach dem Switch ist die maximale Summe der Paare mit $ a_n, a_j, a_k, a_1 $ nicht erhöht. Da andere Paare gleich bleiben, doch nach dem Schalter erhöht sich die maximale Summe aller Paare nicht.

Wenn Sie diesen Prozess fortsetzen, werden wir sicherstellen, dass die verbleibende Anzahl der größten Zahl mit der kleinsten Anzahl in jeder Runde gepaart wird. Die maximale Summe der Paare erhöht sich niemals auf jeder Runde. Nach dem $ N / 2 $ Runden erreichen wir die Pairing, in der $ A_K $ mit $ A_ {n + 1-k} $ .

Sie können sehen, dass der obige Ansatz in der Tat ist, dass sich die "gierigen Aufenthalte" angehen.