[esperti]Algo per trovare 3 elementi in un array che sommati tra di loro sono = 100

[xnavigator]

Allora ragazzi ho questo problema:

ho un array, e devo trovare 3 elementi di quest'array che sommati tra di loro facciano un certo risultato (mettiamo in questo caso 100)

Io avevo pensato ad una soluzione che era O(n^2*logn):
praticamente 2 cicli for innestati (n^2) + una ricerca (logn) per arrivare al valore target.

Il prblema è che mi si chiedeva una soluzione più veloce di n^2*logn, avevo pensato alla programmazione dinamica con tecnica della memoization, ma sinceramente non saprei come impostarla perchè meno di due cicli for per trovare 3 numeri non ne ho idea di come fare...

qui intanto l'algo che avevo trovato io:

    for($i=0;$i<$size;$i++)    {
        for($j=0;$j<$size;$j++) {
            if ($j==$i)
                continue;

                $current = $array[$i] + $array[$j];
                if (array_search($target-$current,$array))
                    die('Found');
            
        }
    } 

[YuYevon]

L'approccio con la programmazione dinamica è possibile ed è forse la strada giusta anche se ora mi risulta difficile ragionarci, causa ruggine e poco tempo a disposizione (ho CPD proprio domani ;_;)... quello che è certo è che anche nell'algoritmo che hai presentato tu si può introdurre una miglioria, anche se di fondo la complessità asintotica rimane la stessa.

Si considera infatti che, per ogni valore di i, tu hai già sommato l'iesimo elemento dell'array a tutti quelli che stanno prima... per esempio, se i vale 3 (partendo da 0) tu avrai già sommato il quarto elemento ai primi tre nelle iterazioni precedenti, ad esempio con

3 5 8 9 10

quando i vale 3 e stai considerando quindi 9, avrai già sommato questo numero ai 3 precedenti (3, 5 e 8) rispettivamente quando i valeva 0, 1 e 2 e j 3, quindi è inutile rifare i calcoli.

Direi di riscrivere così

for($i=0;$i<$size;$i++)    {
        for($j=$i + 1;$j<$size;$j++) {

                $current = $array[$i] + $array[$j];
                if (array_search($target-$current,$array))
                    die('Found');
            
        }
    }

in questo modo non hai più N^2*log_2(N) ma N*(N+1)/2 * log_2(N), quindi fai circa la metà delle iterazioni, però come dicevo non migliora la complessità asintotica.

[xnavigator]

si il problema come hai già detto tu rimane la notazione asintotica che non cambia..

io avevo pensato ad una soluzione greedy che si spingeva fino a toccare O(n*logn). Il problema è che con questa soluzione non è assicurata la soluzione del prolbema per alcune disposizioni di array..

l'algo praticamente ordina l'array in senso crescente poi prende una coppia di valori, essendo ordinato in senso crescente prende ogni volta il primo e l'ultimo, il secondo e il penultimo ecc e poi effettua la ricerca in logn:

for($i=0;$i<(int)$size/2;$i++) {
    $current = $array[$i] + $array[($size-1)-$i];
    $searchArray = $array;
    unset($searchArray[$i],$searchArray[($size-1)-$i]);
    if ( ($j=array_search(($target-$current),$searchArray))!==FALSE ) {
        die('Found')
    }
} 

questo addirittura non si cicla nemmeno tutto l'array perchè prendendo ogni volta una coppia di chiavi il for è fino a size/2

il fatto è che non sempre trova la soluzione

(in bocca al lupo per domani)

[xnavigator]

up

[xnavigator]

mi aspettavo almeno un piccolo parere da oregon/mitaly/macapp

sarà l'estate saranno in ferie anche loro

[frankitt]

La soluzione si trova qui http://www.dsi.uniroma1.it/~asd2/ASDII020707Sol.pdf, con il primo esercizio.
È inutile aggiungere altro quando la soluzione è scritta da un professore capace come quello!
Se non ti è chiaro chiedi pure, solo che pure io è un pò che non tocco quella roba, e nel caso ti posso aiutare tra un pò di giorni, perchè ora non sono a casa...

[xnavigator]

Originariamente inviato da frankitt
La soluzione si trova qui http://www.dsi.uniroma1.it/~asd2/ASDII020707Sol.pdf, con il primo esercizio.
È inutile aggiungere altro quando la soluzione è scritta da un professore capace come quello!
Se non ti è chiaro chiedi pure, solo che pure io è un pò che non tocco quella roba, e nel caso ti posso aiutare tra un pò di giorni, perchè ora non sono a casa...

quello mi sembra un problema diverso (facilmetne riconducibile alla prog dinamica, come lo zaino, quindi esce O(Mn)) perchè la semplicemtne chiede di ottenre M come somma ma utilizzando al più t numeri dell'array.

io devo ottenere M come somma ma utilizzando solo e soltanto 3 numeri

non vedo come si possa modificare quell'algo per il mio caso

grazie per il tuo intervento cmq

[frankitt]

Dati n interi positivi x1 , x2 , . . . xn e due interi M ≥ 0 e t ≥ 0, vogliamo sapere se è possibile ottenere M come somma di al più t degli n numeri.

ho un array, e devo trovare 3 elementi di quest'array che sommati tra di loro facciano un certo risultato (mettiamo in questo caso 100)

Se nel testo metti 100 al posto di M, e 3 al posto di t credo che sia la stessa cosa...

[xnavigator]

Originariamente inviato da frankitt
Se nel testo metti 100 al posto di M, e 3 al posto di t credo che sia la stessa cosa...

no perchè come è scritto quell'algoritmo (la funzione) ritorna TRUE anche se ha ottenuto 100 con soli 2 numeri

[frankitt]

Ho capito cosa intendi, ma il senso dell' esercizio è quello, quindi senza fare esponenziali, basta quella matrice, e tenersi qualche informazione in più.