разбить последовательность из 2n действительных чисел так, чтобы

Question

Я сейчас читаю Руководство по разработке алгоритма , и я застрял в этом упражнении.

---

Возьмите последовательность из 2n действительных чисел в качестве входных данных. Разработать алгоритм O (n log n), который разбивает числа на n пар со свойством, которое разбиение минимизирует максимальная сумма пары. Например, скажем, нам даны цифры (1,3,5,9). Возможные разделы: ((1,3), (5,9)), ((1,5), (3,9)) и ((1,9), (3,5)). Пара суммы для этих разделов: (4,14), (6,12) и (10,8). Таким образом, третий раздел имеет 10 в качестве максимальной суммы, которая является минимальной для трех разделов.

---

По некоторым примерам я думаю, что решение выглядит так:

# in pseudo ruby code
a = [1,3,5,9]
pairs = []
while !a.empty?
    pairs << [a.shift, a.pop]  # [a.first, a.last]
end
pairs

Но как это доказать?

Answer 1

Алгоритм работает, потому что когда x ₀ , x ₁ , ... x _2n-1 - отсортированный список, всегда есть оптимальное решение который содержит (x ₀ , x _2n-1 ).

Доказательство:

Рассмотрим любое оптимальное решение, которое содержит , а не (x ₀ , x _2n-1 ). Он должен содержать пары (x ₀ , x _a ) и (x _b , x _2n-1 ) с x ₀ ≤ x _a ≤ x _2n-1 и x ₀ ≤ x _b ≤ x _2n-1 . Удалите эти пары из раствора и на их место поставьте (x ₀ , x _2n-1 ) и (x _a , x _b ). Может ли присутствие любой новой пары «повредить» решение? Пара (x ₀ , x _2n-1 ) не может иметь, поскольку ее сумма меньше или равна сумме (x _b , x _2n-1 ), который был членом оригинального, оптимального решения. И снова (x _a , x _b ) не могли причинить ущерб, поскольку его сумма меньше или равна сумме (x _b , x *). 1063 * 2n-1 ), который был членом того же решения. Мы построили оптимальное решение, которое содержит (x ₀ , x _2n-1 ).

Таким образом, алгоритм, который вы даете, никогда не исключает возможности найти оптимальное решение на любом шаге, и, когда остается только два значения для спаривания, они должны быть соединены вместе.

Answer 2

С учетом входного массива

x ₀ x ₁ x ₂ ... x _2n

использовать сортировку слиянием для сортировки за O (n log n), чтобы создать отсортированный список

x _{a 0} x _{a 1} ... x _{a 2n}

где индексы _i указывают на перестановку, которую вы выполнили в начальном списке для получения второго списка.

Я утверждаю, что спаривание, которое дает минимальную максимальную сумму по всем спариваниям, является следующим спариванием:

(x _{a i} , x _{a 2n-i} ) для i = 0, 1, ..., n , То есть вы группируете наибольшее число с самым низким доступным числом.

Доказательство

Продолжайте по индукции, для случая 2n = 2 это очевидно.

Без ограничения общности учтите, что входные данные представляют собой список отсортированных чисел (поскольку, если это не так, сортируйте их)

x ₀ x ₁ x ₂ ... x _2n .

Рассмотрим спаривание x _2n с любым числом, тогда ясно, что минимальная сумма этого спаривания достигается с помощью (x _2n , x ₀ ).

Теперь рассмотрим сопряжение x _2n-1 , либо (x _2n , x ₀ ), (x _2n-1 , x ₁ ) - это пары, которые образуют минимальную максимальную сумму, или (x _2n , x ₁ ), (x _2n-1 , x ₀ ) есть, или оба есть. В последнем случае наш выбор не имеет значения. В секундах до последнего случая это невозможно (подумайте об этом). В общем случае, если мы будем индуктивно следовать этому процессу, когда мы ищем пару для x _2n-k , x _k - самое низкое неиспользуемое значение, с которым мы можем соединиться; Предположим, вместо этого мы объединяем x _k с некоторыми другими x _2n-j для j 2n-j + x _k > = x _2n-k + x _k , поэтому в большинстве случаев мы можно достичь только той же минимальной суммы.

Это означает, что выбор (x _2n-k , x _k ) дает нам минимальные пары.

Answer 3

Я думаю, что могу доказать это для последовательности без дублированных чисел, и читателю должно быть достаточно простое упражнение для расширения доказательства на неуникальные последовательности.

Соедините x ₀ , x _2n вместе, затем соедините все остальные числа в соответствии с оптимальным решением.

Теперь рассмотрим сопряжение (x ₀ , x _2n ) с любой другой парой x _y , x _z из оптимальное подмножество. x _2n + x _y или x _z будет больше, чем x _y + x _z , а также x _2n + x ₀ , поэтому спаривание x _2n , x ₀ было оптимальным.

Доказательство теперь распространяется по индукции на спаривание X ₁ , X _2n-1 и дальнейших разбиений подмножества, что в итоге приводит к спариванию OP.