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

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

Poveste și cerință...

Se dă o mulțime formată din _N_ obiecte, fiecare fiind caracterizat de o greutate și un profit.
 
h2. Cerință
 
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

Fișierul de intrare $rucsac1.in$ ...

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

Î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$
* $1 ≤ _W[~i~]_, _P[~i~]_ ≤ 10 000$

h2. Exemplu
table(example).
|_. rucsac1.in |_. rucsac1.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

...

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