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!
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. " –
Sembra il problema dello zaino travestito. –
@ n.m. più come il problema della partizione, come menzionato da Mark ... ma c'è un ulteriore vincolo: lo stesso numero di elementi ... – amit