051 Problema rucsacului

[•GavrilaVlad]

Aici puteţi discuta despre problema Problema rucsacului.

[•PlayLikeNeverB4]

Nu cumva luand toate obiectele mai putin al 3-lea se obtine un profit de 29 iar greutatea lor e 10 ?

[•GavrilaVlad]

Ba da, asa este. Am modificat.

[•ctlin04]

Imi spune cineva cum pot lua suta in pascal, am TLE pe patru teste si chiar nu stiu ce sa mai optimizez?

[•SpiderMan]

Cred ca e limita aiurea pt. pascal nu stiu, incearca sa scoti if-ul ala si sa faci dintr-una, cu un indice P pe care-l modifici cum vrei : P := 1 - P, P := P xor 1 sau faci cu 2 indici, P si Q, pe care-i interschimbi . Daca asa nu merge, raporteaza lui Vlad sa vezi ce zice el .

[•costyv87]

 "Raspunsul final se va afla in starea D[N][G]. "
Nu cumva solutia se gasi pe linia N , fiind max(D[N], 0<=i<=G) ? 

[•costyv87]

"Raspunsul final se va afla in starea D[N][G]. "
Nu cumva solutia se gasi pe linia N , fiind max(D[N], 0<=i<=G) ? 

pardon,  max(D[N][i ], 0<=i<=G)

[•PlayLikeNeverB4]

max(D[i][j] , 0<=j<=G) = D[i][G], pentru orice linie i.

[•costyv87]

 

max(D[i][j] , 0<=j<=G) = D[i][G], pentru orice linie i.

Nu e necesar pentru intreaga matrice deoarece cele mai mari valori se vor transmite oricum pe ultima linie. Ceea ce voiam eu sa zic e ca in solutia problemei e scris gresit . Solutia nu se afla intotdeauna pe D[n][g], ci cu siguranta pe ultima linie.   

[•PlayLikeNeverB4]

Eu am scris o relatie adevarata, nu o operatie pe care trebuie sa o efectuam. Nu inteleg ce vrei sa spui. Intr-un rucsac de capacitate G+1 poti sa pui obiecte de cel putin aceeasi valoare ca si intr-unul de capacitate G.

[•alexandru70]

E corecta limita 0<= W_i <= G? Pentru ca daca W_i==0 si P_i!=0 atunci profitul maxim e infinit, deoarece putem adauga la infinit obiectul i.   

[•SebiSebi]

In enunt este precizat : "submultime de obiecte" => un obiect poate fi folosit cel mult o data.