| Fişierul intrare/ieşire: | ruksak.in, ruksak.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 16 |
| Autor | Florin Chirica | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
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.
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 Wi si Pi, reprezentand greutatea, respectiv profitul obiectului i.
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.
Restricţii
- 1 <= N <= 3 * 105
- 1 <= G <= 3000
- 0 <= Wi, Pi <= 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 :*
Exemplu
| ruksak.in | ruksak.out |
|---|---|
| 6 10 3 7 3 4 1 2 1 9 2 4 1 5 | 29 |
Explicaţie
Luam obiectele 1, 2, 4, 5 si 6, a caror greutate este 10, iar suma profiturilor este 29.
Indicatii de rezolvare
Ati vrea voi golanasilor!
Trebuie sa te autentifici pentru a trimite solutii. Click aici
