N números, pares n / 2.Minimizar a soma máxima de um pareamento.Provando algoritmo ganancioso

Question

Então diga que tenho n números, onde n é mesmo. Eu quero emparelhar os números de modo que a soma máxima dos pares é minimizada. Por exemplo -2, 3, 4, 5. O emparelhamento ideal é (-2, 5), (3, 4), uma vez que a sua soma máxima é 3 + 4= 7, e essa é a quantia mínima possível para uma soma máxima em qualquer emparelhamento. A chave para o algoritmo é ordenar os valores de menos para o maior. Em seguida, pare o menor com o maior, e assim por diante, até chegar ao centro da encomenda.

Exemplo: 3, -2, 4, 5

algoritmo classifica os valores: -2, 3, 4, 5

Então pares primeiro com o último: (-2, 5)

Em seguida, pare o próximo disponível primeiro e último: (3, 4)

Terminate desde que não há pares.

Este é um algoritmo ganancioso e estou tentando provar que está sempre correto usando uma abordagem "gananciosa à frente". Meu problema é que estou lutando para mostrar que a soma máxima do algoritmo é sempre $ \ leq $ soma máxima ideal. Minha intenção era supor para a contradição de que a soma máxima ideal é $ << / span> a soma máxima do algoritmo. Mas não tenho certeza de como encontrar uma contradição. Como esta prova iria?

Answer 1

Você pode ver por que $ \ max ((- 2) +5, 3 + 4) \ lt \ max (-2 + 3, 4 + 5) $ ?

O motivo é simples. Porque no lado direito, o número máximo 5 não é emparelhado com o número mínimo.

---

.

Deixe os números são $ a_1 \ le A_2 \ le \ cdots \ le a_n $ . Deixe os números serem pareados de alguma forma.

• Se $ a_n $ é emparelhado com $ a_1 $ , terminamos neste rodada.

• suponha $ a_n $ é emparelhado com $ a_j $ , $ j \ não= 1 $ . Em seguida, $ a_1 $ é emparelhado com $ a_k $ para alguma $ k \ não= n $ . Então temos dois pares, $ {A A_N, A_J} $ e $ \ {a_1, a_k \} $ << / span>. As somas desses dois pares são $ a_n + a_j $ e $ a_1 + a_k $ , o grande do que é $ a_n + a_j $ .

  Deixe-nos alternar $ a_j $ e $ a_1 $ para que $ a_n $ vai parear com $ a_1 $ , e $ a_j $ Par com $ a_k $ . As somas dos dois novos pares são $ a_n + a_1 $ e $ a_j + a_k $ , ambos que é no máximo $ a_n + a_j $ , ou seja, o grande deles é no máximo $ a_n + A_J $ < / span>. Então, depois do switch, a soma máxima dos pares envolvendo $ a_n, A_J, A_K, A_1 $ não aumenta. Como outros pares permanecem os mesmos, então depois do interruptor, a soma máxima de todos os pares não aumenta.

Continuando este processo, vamos garantir que o maior número restante seja parecido com o menor número restante em cada rodada. A soma máxima dos pares nunca aumentará em cada rodada. Após $ n / 2 $ rodadas, chegaremos ao emparelhamento onde $ a_k $ é emparelhado com $ a_ {n + 1-k} $ .

Você pode ver a abordagem acima é de fato que a abordagem "gananciosa permanece à frente".