== include(page="template/taskheader" task_id="ruksak") ==
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.
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
Pe prima linie a fişierul ruksak.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 $ruksak.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 ruksak.out se va afisa o singura valoare Pmax, profitul maxim care poate fi obtinut respectand conditia problemei.
În fişierul de ieşire $ruksak.out$ se va afisa o singura valoare $Pmax$, profitul maxim care poate fi obtinut respectand conditia problemei.
h2. Restricţii
* 1 <= N <= 10^6
* 1 <= G <= 2000
* 0 <= Wi, Pi <= 2000
* $1 <= N <= 3 * 10^5^$
* $1 <= G <= 3000$
* $0 <= W[~i~], P[~i~] <= 3000$
* $Multumiri speciale lui Vlad Gavrila pentru enuntul problemei rucsac, caruia i-am dat copy-paste aici. Te pupam si te iubim, cel mai dulce baiat :*$
h2. Exemplu
table(example). |_. ruksak.in |_. ruksak.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 10
3 7
3 4
1 2
1 9
2 4
1 5
| 29
|
h3. Explicaţie
...
Luam obiectele $1, 2, 4, 5$ si $6,$ a caror greutate este $10,$ iar suma profiturilor este $29$.
h3. Indicatii de rezolvare
Ati vrea voi golanasilor!
== include(page="template/taskfooter" task_id="ruksak") ==
