N numeri, n / 2 coppie.Ridurre al minimo la somma massima di un abbinamento.Proving algoritmo avido

Question

Quindi dici che ho n numeri, dove n è pari. Voglio abbinare i numeri in modo tale che la somma massima delle coppie sia ridotta al minimo. Ad esempio -2, 3, 4, 5. L'abbinamento ideale è (-2, 5), (3, 4), poiché la sua somma massima è 3 + 4= 7, e questa è la somma minima possibile per una somma massima in qualsiasi abbinamento. La chiave per l'algoritmo è quella di ordinare i valori da meno del più grande. Quindi accoppia il minimo con il massimo, e così via, fino a raggiungere il centro dell'ordine.

Esempio: 3, -2, 4, 5

Algoritmo Ordina i valori: -2, 3, 4, 5

Quindi coppie prima con l'ultima volta: (-2, 5)

Quindi coppie il prossimo disponibile prima e ultimo: (3, 4)

termina dal momento che non sono rimaste coppie.

Questo è un algoritmo avido e sto cercando di dimostrare che è sempre corretto utilizzando un approccio "avido rimane avanti". Il mio problema è che sto lottando per mostrare che la somma massima dell'algoritmo è sempre $ \ leq $ somma massima ottimale. La mia intenzione doveva supporre per contraddizione che la somma massima ottimale è $ <$ la somma massima dell'algoritmo. Ma non sono sicuro di come trovare una contraddizione. Come dovrebbe andare questa prova?

Answer 1

Puoi vedere perché $ \ max (((- 2) +5, 3 + 4) \ lt \ max (-2 + 3, 4 + 5) $ ?

La ragione è semplice. Poiché sul lato destro, il numero massimo 5 non è accoppiato con il numero minimo.

---

.

Lascia che i numeri siano $ a_1 \ le a_2 \ le \ cdots \ le a_n $ . Lascia che i numeri siano abbinati in qualche modo.

.

• se $ a_n $ è accoppiato con $ a_1 $ , abbiamo fatto in questo round.

• Supponiamo $ a_n $ è accoppiato con $ a_j $ , $ j \ no= 1 $ . Quindi $ A_1 $ è accoppiato con $ a_k $ per alcuni $ k \ not= n $ . Quindi abbiamo due coppie, $ {a_n, a_j \} $ e $ \ {A_1, A_K \} $ < / span>. Le somme di queste due coppie sono $ a_n + a_j $ e $ a_1 + a_k $ , il grande Di cui è $ a_n + a_j $ .

  Svitaccendiamo $ A_J $ e $ a_1 $ in modo che $ A_N $ Accoppia con $ A_1 $ e $ a_j $ Coppia con $ a_k $ . Le somme delle due nuove coppie sono $ a_n + a_1 $ e $ a_j + a_k $ , entrambi che è al massimo $ a_n + a_j $ , cioè, l'ampio di loro è al massimo $ a_n + a_j $ < / span>. Quindi, dopo l'interruttore, la somma massima delle coppie che coinvolgono $ a_n, A_J, A_K, A_1 $ non aumenta. Poiché altre coppie rimangono uguali, quindi dopo l'interruttore, la somma massima di tutte le coppie non aumenta.

Continuando questo processo, ci assicureremo che il numero più grande rimanente sia accoppiato con il numero più piccolo rimanente ad ogni round. La somma massima delle coppie non aumenterà mai ad ogni round. Dopo $ N / 2 $ round, raggiungeremo l'accoppiamento dove $ a_k $ è accoppiato con $ a_ {n + 1-k} $ .

Puoi vedere l'approccio di cui sopra è davvero l'approccio "Greedy rimane avanti".