n数字、n / 2ペア。ペアリングの最大和を最小限に抑えます。証明された貪欲なアルゴリズム

Question

だから私はn個の数字を持っています、ここでnは偶数です。ペアの最大合計が最小化されるように番号をペアにしたいです。例えば、-2,3,4,5の場合、理想的なペアリングは（-2,5）、（3,4）、その最大和は3 + 4= 7であり、最大の合計で可能な最小限の和です。どんなペアリングでも。アルゴリズムの鍵は、最低から最大まで値を並べ替えることです。次に、注文の中心に達するまで、最も絶対的なものとペアロードします。

実施例：3、-2,4,5

アルゴリズムの値をソートします。-2,3,4,5

その後、最後に最初にペア：（-2,5）

その後、次の最初の利用可能と最後のペア：（3,4）

ペアが残っていないので終了します。

これは貪欲なアルゴリズムであり、「貪欲な滞在」アプローチを使用して常に正しいことを証明しようとしています。私の問題は、アルゴリズムの最大合計が常に $ \ leq $ の最適最大値であることを示すのに苦労しています。私の意図は、最適な最大合計が $ <$ であると矛盾することでした。アルゴリズムの最大合計。しかし、矛盾を見つける方法はわかりません。この証明はどのようになりますか？

Answer 1

$ \ max（（ - 2）+ 5,4 + 4）\ ？

理由は簡単です。右側には最大数5が最小数とペアになっていないため、

---

数字は $ A_1 \ LE A_2 \ LE \ CDOTS \ LE A_N $ です。数字をいくつかの方法でペアにしましょう。

• $ a_n $ の場合 $ a_1 $ とペアになっていますが、これで終わります。ラウンド。

• $ a_n $ がペアに対応しています $ a_j $ 、 $ J \ NOT= 1 $ 。その後、 $ A_1 $ は、 $ a_k $ とペアに対応しています $ k \ not= n $ 。そのため、 $ \ {a_n、a_j \} $ と $ \ {a_1、a_k \} $ < /スパン>。これら2つのペアの合計は、 $ A_N + A_J $ と $ A_1 + A_K $ 、大きなものです。そのうちspan class="math-container"> $ a_n + a_j $ です。

  $ a_j $ と $ a_1 $ を切り替えますので、 $ A_n $ は $ A_1 $ とペアになり、 $ a_j $ $ a_k $ とペア。 2つの新しいペアの合計は $ A_n + A_1 $ と $ a_j + a_k $ です。これは $ a_n + a_j $ です。つまり、それらの大きい方は $ A_n + A_J $ <です。 /スパン>。そのため、スイッチの後、 $ a_n、a_j、a_k、a_1 $ を含むペアの最大和は増えません。他のペアは同じままであるので、スイッチの後、すべてのペアの最大合計は増加しません。

このプロセスを継続して、残っている最大数が各ラウンドに残っている最小数とペアになることを確認します。ペアの最大合計はそれぞれのラウンドでは増加しません。 $ n / 2 $ ラウンドの後、 $ a_k $ が $ a_ {n + 1-k} $ 。

上記のアプローチが確かに「貪欲な滞在」アプローチです。