h3. Sobo

Problema se rezolva prin programare dinamica. Se retine in $A{~i~}$ = costul minim in cazul cel mai defavorabil pentru a recunoaste sobolanul inteligent din multimea de sobolani cu numerele de ordine pozitiile bitilor de $1$ in reprezentarea binara a lui {$i$}. Astfel, $A$ va avea valori pentru $i$ intre $0$ si {$2^N-1^$}. Raspunsul va fi {$A{~2^N-1^~}$}. Este evident ca graful format de aceste stari este aciclic deoarece fiecare raspuns imparte o multime in doua multimi mai mici. Astfel pentru a calcula un $A{~i~}$ vom lua fiecare raspuns care imparte in doua multimi nevide multimea curenta, vom vedea in care multime costul este mai mare (cazul cel mai defavorabil) , adaugam pretul raspunsului si actualizam in $A{~i~}$ daca valoarea aceasta este mai mica decat cea curenta (sa nu uitam ca vrem cost minim in cazul cel mai defavorabil). Cea mai simpla metoda de a implementa acest mecanism este cu memoizare. Complexitatea finala {$O(2^N^ * L * N)$}. Se poate optimiza la {$O(2^N^ * L)$} folosind operatii pe biti.

Problema se rezolva prin programare dinamica. Se retine in $A{~i~}$ = costul minim in cazul cel mai defavorabil pentru a recunoaste sobolanul inteligent din multimea de sobolani cu numerele de ordine pozitiile bitilor de $1$ in reprezentarea binara a lui {$i$}. Astfel, $A$ va avea valori pentru $i$ intre $0$ si {$2^N^-1$}. Raspunsul va fi {$A{~2^N^-1~}$}. Este evident ca graful format de aceste stari este aciclic deoarece fiecare raspuns imparte o multime in doua multimi mai mici. Astfel pentru a calcula un $A{~i~}$ vom lua fiecare raspuns care imparte in doua multimi nevide multimea curenta, vom vedea in care multime costul este mai mare (cazul cel mai defavorabil) , adaugam pretul raspunsului si actualizam in $A{~i~}$ daca valoarea aceasta este mai mica decat cea curenta (sa nu uitam ca vrem cost minim in cazul cel mai defavorabil). Cea mai simpla metoda de a implementa acest mecanism este cu memoizare. Complexitatea finala {$O(2^N^ * L * N)$}. Se poate optimiza la {$O(2^N^ * L)$} folosind operatii pe biti.