Fișierul intrare/ieșire rucsac1.in, rucsac1.out Sursă Infoarena
Autor teorie Adăugată de avatar Marcela Marcela Marcela
Timp de execuție pe test 0.4 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii