rucsac

Rucsac

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

Poveste şi cerinţă...

Se da o multime formata din $N$ obiecte, fiecare fiind caracterizat de o greutate si un profit. 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$.

h2. Date de intrare

Fişierul de intrare $rucsac.in$ ...

Pe prima linie a fişierul $rucsac.in$ se vor gasi valorile $N$ si $G$, cu semnificatia din enunt. Pe urmatoarele $N$ linii se vor gasi 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 $rucsac.out$ ...

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

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 5000$
* $1 ≤ G ≤ 10000$

h2. Exemplu