Fișierul intrare/ieșire | rucsac1.in, rucsac1.out | Sursă | Infoarena |
---|---|---|---|
Autor | teorie | Adăugată de | Marcela • Marcela |
Timp de execuție pe test | 0.4 sec | Limită de memorie | 8192 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Rucsac 1
Se dă o mulțime formată din N obiecte, fiecare fiind caracterizat de o greutate și un profit.
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.
Date de intrare
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 Wi si Pi, reprezentand greutatea, respectiv profitul obiectului i.
Date de ieșire
În fișierul de ieșire rucsac1.out se va afisa o singura valoare Pmax, profitul maxim care poate fi obținut respectînd condiția problemei.
Restricții
- 1 ≤ N ≤ 5000
- 1 ≤ G ≤ 10 000
- 1 ≤ Wi, Pi ≤ 10 000
Exemplu
rucsac1.in | rucsac1.out |
---|---|
6 10 3 7 3 4 1 2 1 9 2 4 1 5 |
29 |
Explicație
Luăm obiectele 1, 2, 4, 5 si 6, a căror greutate este 10, iar suma profiturilor este 29.