Fişierul intrare/ieşire:rucsac1.in, rucsac1.outSursăInfoarena
AutorTeorieAdăugată deMarcelaMarcela Marcela
Timp execuţie pe test0.4 secLimită de memorie8192 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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
  • 0 ≤ Wi, Pi ≤ 10 000

Exemplu

rucsac1.inrucsac1.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici