infoarena

Aici puteţi discuta despre problema Problema rucsacului (http://infoarena.ro/problema/rucsac).

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

Ba da, asa este. Am modificat. :)

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

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 :).

 "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) ? 

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.   :P

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.

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.   

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