2011-10-02 40 views
6

Sto cercando lavoro ora e sto facendo molti esercizi con l'algoritmo. Ecco il mio problema:- trova la sottrazione minima tra la somma di due array


Date due matrici: un e b con stessa lunghezza, il soggetto è quello di rendere | sum (a) -SUM (b) | minimo, scambiando elementi tra a e b.


Ecco il mio però:

assumere ci scambiamo a [i] e B [j], impostare Delt = somma (a) - sum (b), x = a [i] -b [j]
quindi Delt2 = somma (a) -a [i] + b [j] - (somma (b) -b [j] + a [i]) = Delt - 2 * x,
quindi il cambia = | Delt | - | Delt2 |, che è proporzionale alla | Delt |^2 - | Delt2 |^2 = 4 * x * (Delt-x),

Sulla base del pensiero di cui sopra ho ricevuto il seguente codice:


Delt = sum(a) - sum(b); 
done = false; 
while(!done) 
{ 
    done = true; 
    for i = [0, n) 
    { 
     for j = [0,n) 
     { 
      x = a[i]-b[j]; 
      change = x*(Delt-x); 
      if(change >0) 
      { 
       swap(a[i], b[j]); 
       Delt = Delt - 2*x; 
       done = false; 
      } 
     } 
    } 
} 

Tuttavia, qualcuno ha una soluzione molto migliore? Se hai, per favore dimmelo e ti sarei molto grato!

+0

Il tuo problema è equivalente a "Dato un array a con lunghezza 2 * n e somma (a) = 2 * S, trova esattamente n elementi nella matrice il cui totale è il più vicino possibile a S. " –

+1

Sembra il problema dello zaino travestito. –

+0

@ n.m. più come il problema della partizione, come menzionato da Mark ... ma c'è un ulteriore vincolo: lo stesso numero di elementi ... – amit

risposta

3

Questo problema è fondamentalmente il problema di ottimizzazione per Partition Problem con un vincolo aggiuntivo di parti uguali. Dimostrerò che l'aggiunta di questo vincolo non semplifica il problema.

NP-Hardness prova:
Assumere c'era un algoritmo A che risolve questo problema in tempo polinomiale, siamo in grado di risolvere il Partition-Problem in tempo polinomiale.

Partition(S): 
for i in range(|S|): 
    S += {0} 
    result <- A(S\2,S\2) //arbitrary split S into 2 parts 
    if result is a partition: //simple to check, since partition is NP. 
    return true. 
return false //no partition 

Correttezza:
Se c'è una partizione indicare come (S1, S2) [assumere S2 ha più elementi], sulla iterazione | S2 | - | S1 | [Cioè quando si aggiunge | S2 | - | S1 | zeri]. L'input su A contatterà abbastanza zeri in modo che possiamo restituire due array di uguale lunghezza: S2, S1 + {0,0, ..., 0}, che sarà una partizione a S e l'algoritmo produrrà true.
Se l'algoritmo restituisce true e l'iterazione k, disponevamo di due array: S2, S1, con lo stesso numero di elementi e valori uguali. rimuovendo gli zeri k dagli array, otteniamo una partizione S originale, quindi S ha una partizione.

polinomiale:
assumere A prende P(n) tempo, l'algoritmo abbiamo prodotto avrà n*P(n) tempo, che è anche polinomiale.

Conclusione:
Se questo problema è solveable in tempo polinomiale, così fa il Partion-problema, e quindi P = NP. basato su questo: questo problema è NP-Hard.

Poiché questo problema è NP-Hard, per una soluzione esatta è necessario un algoritmo esponenziale. Uno di questi è semplice backtracking [lascio come esercizio al lettore di implementare una soluzione backtracking]

EDIT: come detto da @jpalecek: semplicemente creando una riduzione: S->S+(0,0,...,0) [k volte 0], uno può dimostrare direttamente la NP-Hardness riducendo. il polinomio è banale e la correttezza è molto simile alla prova di correttezza della suddetta parodia: [se esiste una partizione, è possibile aggiungere zeri 'bilanciati'; l'altra direzione è semplicemente tagliando quegli zeri]

+0

Credo che tu abbia sbagliato il rientro - perché dovresti eseguire 'result <- A (S \ 2, S \ 2)' n volte? A proposito, quello che hai scritto non è la riduzione polinomiale che usiamo per dimostrare la durezza NP. – jpalecek

+0

@jpalecek: Sto eseguendo 'A (S/2, S/2)' una volta ogni passo, e controllo per una possibile soluzione con il numero di k di 'k', dove' k' è il numero di iterazione. Non sto usando una riduzione qui, sto provando che se esiste un tale algoritmo, P = NP, che equivale a dire che questo algoritmo è NP-Hard. [perché è chiaramente NP, e se P = NP allora P = NP = NP-Completo] – amit

+0

Il problema è che devi usare una riduzione per dimostrare la durezza NP, perché la durezza NP è definita in termini di riduzione. Quello che hai provato è 'Partizione \ in P^A', ma non segue (almeno non direttamente) che A sia NP completo. Inoltre, se hai appena aggiunto tutti gli zeri e chiesto ad A una volta, funzionerebbe anche tu e avresti una riduzione. – jpalecek

0

Solo un commento. Attraverso tutto questo scambio puoi sostanzialmente organizzare il contenuto di entrambi gli array come preferisci. Quindi non è importante in quale array i valori sono all'inizio.

Non posso farlo nella mia testa, ma sono abbastanza sicuro che ci sia una soluzione costruttiva. Penso che se li ordinerai prima e poi li gestirò secondo alcune regole. Qualcosa lungo le linee If value > 0 and if sum(a)>sum(b) then insert to a else into b