Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2011-08-12 11:07:28.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | rucsac.in, rucsac.out | Sursă | Arhiva Educationala |
| Autor | Arhiva Educationala | Adăugată de |  Gavrila Vlad •GavrilaVlad |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Problema rucsacului
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şierul rucsac.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 rucsac.out se va afisa o singura valoare Pmax, profitul maxim care poate fi obtinut respectand conditia problemei.
Restricţii
- 1 ≤ N ≤ 5000
- 1 ≤ G ≤ 10000
- 0 ≤ Wi, Pi ≤ 10000
Exemplu
| rucsac.in | rucsac.out |
|---|---|
| 6 10 3 7 3 4 1 2 1 9 2 4 1 5 | 27 |
Explicaţie
Luam obiectele 1, 3, 4, 5 si 6, a caror greutate este 8, iar suma profiturilor este 27.
Trebuie sa te autentifici pentru a trimite solutii. Click aici
