Diferențe pentru problema/rucsac1 între reviziile #2 si #9

== include(page="template/taskheader" task_id="rucsac1") ==

Se da o multime formata din N obiecte, fiecare fiind caracterizat de o greutate si un profit.
Poveste și cerință...

Se dă o mulțime formată din _N_ obiecte, fiecare fiind caracterizat de o greutate și un profit.

h2. Cerință

Sa se gaseasca o submultime de obiecte astfel incat suma profiturilor lor sa fie maxima, iar suma greutatilor lor sa nu depaseasca o valoare G.

Să se gasească o submulțime de obiecte astfel încît suma profiturilor lor sa fie maximă, iar suma greutăților lor să nu depașească o valoare _G_.

h2. Date de intrare

Pe prima linie a fișierului de intrare $rucsac1.in$ se vor gasi valorile N si G, cu semnificatia din enunt. Pe urmatoarele N linii se vor gasi perechile de valori Wi si Pi, reprezentand greutatea, respectiv profitul obiectului i.

Pe prima linie a fișierului de intrare $rucsac1.in$ se vor gasi valorile _N_ si _G_, cu semnificația din enunț. Pe următoarele _N_ linii se vor găsi perechile de valori _W[~i~]_ si _P[~i~]_, reprezentand greutatea, respectiv profitul obiectului _i_.

h2. Date de ieșire

În fișierul de ieșire $rucsac1.out$ se va afisa o singura valoare Pmax, profitul maxim care poate fi obtinut respectand conditia problemei.

În fișierul de ieșire $rucsac1.out$ se va afisa o singura valoare _P[~max~]_, profitul maxim care poate fi obținut respectînd condiția problemei.

h2. Restricții

* $1 ≤ N ≤ 5000$
* $1 ≤ G ≤ 10 000$
* $0 ≤ Wi, Pi ≤ 10 000$

* $1 ≤ _N_ ≤ 5000$
* $1 ≤ _G_ ≤ 10 000$
* $1 ≤ _W[~i~]_, _P[~i~]_ ≤ 10 000$

h2. Exemplu

h3. Explicație

Luam obiectele 1, 2, 4, 5 si 6, a caror greutate este 10, iar suma profiturilor este 29.

Luăm obiectele 1, 2, 4, 5 si 6, a căror greutate este 10, iar suma profiturilor este 29.

== include(page="template/taskfooter" task_id="rucsac1") ==