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, 3 + 4) \ lt \ max (-2 + 3, 4 + 5) $ ?

Причина проста. Потому что с правой стороны максимальное количество 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 \ не= n $ . Таким образом, у нас есть две пары, $ \ {a_n, a_j \} $ и $ \ {a_1, a_k \} $ < / span>. Суммы этих двух пар являются $ a_n + a_j $ и $ a_1 + a_k $ , большой из которых $ a_n + a_j $ .

  Давайте переключаем $ a_j $ и $ a_1 $ так, чтобы $ a_n $ будет пару с $ a_1 $ , а $ a_j $ Пара с $ a_k $ . Суммы двух новых пар являются $ a_n + a_1 $ и $ a_j + a_k $ , оба который находится на большинстве $ a_n + a_j $ , т. Е. Большой один из них находится на большинстве случаев $ a_n + a_j $ < / span>. Поэтому после переключателя максимальная сумма пар, включающих $ a_n, a_j, a_k, a_1 $ не увеличивается. Поскольку другие пары остаются прежними, поэтому после коммутатора максимальная сумма всех пар не увеличивается.

Продолжая этот процесс, мы уберемся, что оставшееся наибольшее количество, оставшееся с наименьшим числом, оставшимся в каждом раунде. Максимальная сумма пар никогда не будет увеличиваться в каждом раунде. После $ n / 2 $ раунды, мы достигнем сочетания, где $ a_k $ сочетается с $ a_ {n + 1-k} $ .

Вы можете увидеть, что вышеприведенный подход - это действительно «жадные остается вперед».