Ruksak

ruksak

== 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$.

Poveste şi cerinţă...

h2. Date de intrare

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$.

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

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$ ...

h2. Restricţii

* $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 |

| 6 10
3 7
3 4
1 2
1 9
2 4
1 5
| 29

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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