n 숫자, n / 2 쌍.페어링의 최대 합계를 최소화하십시오.욕심 많은 알고리즘을 증명합니다

Question

그래서 n 숫자가 있다고 말하면서 n은 짝수입니다. 쌍의 최대 합계가 최소화되도록 숫자를 페어링하고 싶습니다. 예를 들어 -2, 3, 4, 5. 이상적인 페어링은 최대 합이 3 + 4= 7이기 때문에 (-2, 5), (3, 4)이며, 최대 합계에 가능한 최소량입니다 어떤 페어링에서. 알고리즘의 열쇠는 값을 가장 적게 가장 잘 정렬하는 것입니다. 그런 다음 주문의 중심에 도달 할 때까지 가장 큰 것과 가장 훌륭한 것으로 가장 적어도 짝을줍니다.

예 : 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 \ not= 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} $ .

위의 접근 방식은 실제로 "탐욕스러운 체류"접근 방식입니다.