infoarena

Pe o strada, se afla un sir de N case (toate pe o singura parte). In fiecare casa i sunt bunuri de o anumita valoare A[i ]. Stiind ca un hot nu ar jefui niciodata 2 case alaturate (pentru a nu fi prins), sa se afle care este profitul maxim care l-ar putea obtine de pe acea strada. Avand in vedere ca se urmareste maximizarea profitului (evident, A[i ]>0), din fiecare casa jefuita hotul va fura toate bunurile disponibile.

Ceva indicii va rog?

Poti construi o functie recurenta profit(i):

cale1= profit(i+1); //se poate sa vrem sa sarim peste o casa pentru a o putea jefui pe cea de dupa ea
Daca nu a fost jefuita casa anterioara cale2= A[i] + profit(i+1); //jefuim casa curenta
return max(cale1,cale2);

Modul in care marchezi cand casa anterioara a fost jefuita decizi tu.

Pai asta e o problema clasica de dinamica.
Am nota prada[ i ] = prada maxima pe care ar lua-o hotul daca jefuieste "optim" in intervalul caselor 1...i,jefuind obligatoriu casa i
Deci prada [ i ] = A[ i ] + max(prada[i-2],prada[i-3]) , cu initializarile prada[0]=0, prada[1]=A[1], prada[2]=A[2] , eventual si prada[3]=A[3]+A[1] , iar recurenta o rulezi pentru i=4,n sau i=3,n

N-am inteles asta cu "jefuieste optim" dar si "jefuind obligatoriu casa i". Eu cred ca nu-ti da bine pe teste de genul asta:

Deci prada[ i ] = prada maxima pe care o poate capata hotul jefuind case in intervalul 1....i ,casa i fiind obligatoriu jefuita.
Am uitat sa precizez ca solutia va fi max(prada[n],prada[n-1]).
Pe exemplul tau vectorul prada va fi :
0 5 1 10 6 11 15 12 20 iar solutia este max(12,20) = 20.  :peacefingers:

Explicatia recurentei este ca prada[ i ] = A[ i ] (pentru ca jefuieste obligatoriu si casa i,deci i-1 nu este jefuita) + max(prada[i-2],prada[i-3]) - adica prada[i-2] ar insemna ca este jefuita si casa i-2 deci i-3 nu este jefuita,iar prada[i-3] inseamna ca i-3 este jefuita,i-2 nefiind in acest caz jefuita

Am inteles maestre :)

Pentru 0 5 1 10 6 11 15 12 20 solutia este 50 :D

Am luat-o ca o secventa dintr-un sir astfel incat suma sa fie maxima fara ca sa poti adauga la suma 2 numere consecutive din sir.

suma[0] = valoareA[0];
      suma[1] = max(suma[0],valoareA[1]);
      for(int i = 2; i < n ; i++)
         suma = max(suma[i-2] + valoareA[ i ] ,suma[i-1]);
Si in suma[n-1] e suma maxima.

0 5 1 10 6 11 15 12 20 la el reprezinta vectorul de solutii, nu acel A.

Da, metoda ta pare mai logica.

Îmi poţi spune, te rog, unde ai găsit această problemă ?

Problema asta (si cel putin inca una postata de userul in cauza - mersi colegului Cosmin pentru avertisment) face parte dintr-un set de probleme pe care le-a primit ca test de aptitudini pentru angajare la o firma de programare. Stiu asta pentru ca eu am fost cel care a propus aceste 2 probleme (printre altele)... tot eu fac si corectarea rezolvarilor trimise de cei care aplica la noi pt un job. Acum 2 zile, ii corectam rezolvarile si ma miram cum reusea sa rezolve problemele de programare dinamica si sa greseasca la altele mult mai usoare - sper ca v-ati dat seama deja ca nu a mai primit postul pentru care a aplicat (sincer, punctajul ar fi fost de trecere, chiar daca au fost cateva probleme destul de grave pe la rezolvarile trimise, dar atitudinea asta nu poate fi trecuta cu vederea - plus ca acum nu mai sunt sigur cate dintre problemele respective le-a rezolvat singur).


Nu pot sa condamn comunitatea infoarena pt ajutorul care i l-a acordat, dar as ruga pe viitor utilizatorii acestui forum sa nu apeleze la ajutorul altora pentru a rezolva problemele date la angajare. Astfel de teste sunt date anume pentru a testa aptitudinile voastre, nu ale altora. Chiar si daca treceti testul de angajare, mai devreme sau mai tarziu nivelul vostru real va iesi la iveala, iar daca pe deasupra sunteti prinsi ca ati copiat la testul de angajare, riscati sa gasiti si mai greu locuri de munca in viitor.

 :rotfl: owned

Am si eu o intrebare , nu vreau sa fiu nepoliticos , dar problemele astea nu se pot da intr-un mediu inchis de-a lungul a 4-5 ore? Asa ar fi mai greu ca cineva sa copieze.