Fişierul intrare/ieşire:ruksak.in, ruksak.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 16
AutorFlorin ChiricaAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inruksak.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

Cum se trimit solutii?