|
Titlul: PD Scris de: Jean Luca Paliuca din Mai 18, 2008, 17:50:14 Salut,I need some help :fool:
Se dau doua cuvinte , primul are pentru fiecare litera un cost asociat. Se cere subsirul comun de cost maxim..Any ideea ? Titlul: Răspuns: PD Scris de: Maria Stanciu din Mai 18, 2008, 18:36:05 Salut :).
In primul rand daca toate costurile sunt pozitive, atunci e logic ca subsirul de cost maxim va fi cel mai lung subsir comun. Pentru a rezolva problema asta te sfatuiesc sa rezolvi mai intai http://infoarena.ro/problema/cmlsc din arhiva educationala. Daca pot exista si costuri negative atunci te sfatuiesc (desi trebuie sa-ti spun ca n-am implementat) ca in matricea de lungimi sa retii de fapt costurile, adica a[k][j]= cel mai mare cost al unui subsir utilizand primele k litere din primul sir si primele j litere din al doilea. Ar trebui sa mearga. Spor la treaba :thumbup: Titlul: Răspuns: PD Scris de: Jean Luca Paliuca din Mai 18, 2008, 18:44:50 Salut :). In primul rand daca toate costurile sunt pozitive, atunci e logic ca subsirul de cost maxim va fi cel mai lung subsir comun. Pentru a rezolva problema asta te sfatuiesc sa rezolvi mai intai http://infoarena.ro/problema/cmlsc din arhiva educationala. Si daca sunt mai multe subsiruri comune de lungime maxima cum sti sa-l iei cel mai mare ? Titlul: Răspuns: PD Scris de: Savin Tiberiu din Mai 18, 2008, 18:58:39 In primul rand daca toate costurile sunt pozitive, atunci e logic ca subsirul de cost maxim va fi cel mai lung subsir comun. Pentru a rezolva problema asta te sfatuiesc sa rezolvi mai intai http://infoarena.ro/problema/cmlsc din arhiva educationala. nu e chiar asa. Pica pe urmatorul test. aba ab Costurile sunt : a->1 b->1 a->100 Subsirul de lungime maxima o sa fie "ab" si o sa aibe cost 2, insa subsirul de cost maxim este "a" si are costul 100. Titlul: Răspuns: PD Scris de: Alina Ene din Mai 18, 2008, 19:38:32 Probabil ca fiecare litera are cost unic (altfel problema nu e bine definita, de ex ab poate avea cost 101). Un exemplu mai clar e bacd, adb cu costuri b : 100, a, c, d : 1. Ideea de DP e foarte similara totusi.
Titlul: Răspuns: PD Scris de: Jean Luca Paliuca din Mai 18, 2008, 19:54:12 Nu sunt neaparat distincte costurile.
So, any solution ? Titlul: Răspuns: PD Scris de: Savin Tiberiu din Mai 18, 2008, 20:13:00 deci cum e pana la urma?? dane un exemplu cum asociezi costurile alea??
Titlul: Răspuns: PD Scris de: Jean Luca Paliuca din Mai 18, 2008, 20:20:24 primul sir : XYXYX
costuri : 2 2 7 1 1 second : XY Solutia e XY cu costul 8 de pe penultimele 2 pozitii din primul sir Titlul: Răspuns: PD Scris de: Alina Ene din Mai 18, 2008, 20:24:48 Pai cam aceeasi solutie ca si pentru subsirul de lungime maxima.
Mai precis, fie s = s_1 .. s_n si t = t_1 .. t_m sirurile initiale. Fie din[ i ][ j ] = costul maxim al unui subsir al sirurilor s_1 .. s_i si t_1 .. t_j. O recurentza e cam asa (cred): din[ i ][ 0 ] = din[ 0 ][ j ] = 0 din[ i ][ j ] = max(0, din[ i - 1 ][ j - 1 ] + cost(s_i), din[ i ][ j - 1 ], din[ i - 1 ][ j ]), daca s_i = t_j = max(0, din[ i ][ j - 1 ], din[ i - 1 ][ j ]), altfel N.B.: ma refeream la faptul ca daca o litera nu are cost unic, notiunea de cost al unui subsir nu e bine definita. Later edit: OK, mi-am dat seama ce vrei sa spui. Titlul: Răspuns: PD Scris de: Jean Luca Paliuca din Mai 21, 2008, 13:04:48 Are vreun rost sa-l pui si pe 0 cand faci maximul :??
Titlul: Răspuns: PD Scris de: Alina Ene din Mai 21, 2008, 13:32:34 Nu e necesar sa pui 0.
|