•the_godfather
Strain
Karma: -6
Deconectat
Mesaje: 26
|
|
« : Iulie 27, 2011, 01:05:42 » |
|
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?
|
|
« Ultima modificare: Iulie 27, 2011, 10:47:58 de către Sima Cotizo »
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #1 : Iulie 27, 2011, 01:20:48 » |
|
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.
|
|
« Ultima modificare: Iulie 27, 2011, 11:41:37 de către George Marcus »
|
Memorat
|
|
|
|
•scipianus
|
|
« Răspunde #2 : Iulie 27, 2011, 08:43:17 » |
|
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
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #3 : Iulie 27, 2011, 11:46:02 » |
|
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:
|
|
|
Memorat
|
|
|
|
•scipianus
|
|
« Răspunde #4 : Iulie 27, 2011, 12:10:39 » |
|
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. 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
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #5 : Iulie 27, 2011, 14:37:53 » |
|
Am inteles maestre
|
|
|
Memorat
|
|
|
|
•the_godfather
Strain
Karma: -6
Deconectat
Mesaje: 26
|
|
« Răspunde #6 : Iulie 28, 2011, 15:13:24 » |
|
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. 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 Pentru 0 5 1 10 6 11 15 12 20 solutia este 50 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.
|
|
|
Memorat
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #7 : Iulie 28, 2011, 15:46:52 » |
|
0 5 1 10 6 11 15 12 20 la el reprezinta vectorul de solutii, nu acel A.
Da, metoda ta pare mai logica.
|
|
|
Memorat
|
|
|
|
•stocarul
|
|
« Răspunde #8 : Iulie 28, 2011, 20:38:11 » |
|
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?
Îmi poţi spune, te rog, unde ai găsit această problemă ?
|
|
|
Memorat
|
|
|
|
•thecata
Strain
Karma: 15
Deconectat
Mesaje: 9
|
|
« Răspunde #9 : Iulie 29, 2011, 15:32:18 » |
|
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.
|
|
|
Memorat
|
|
|
|
|
•crushack
|
|
« Răspunde #11 : Iulie 30, 2011, 18:49:53 » |
|
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.
|
|
|
Memorat
|
|
|
|
|