Fişierul intrare/ieşire:rucsacfr.in, rucsacfr.outSursăad-hoc
AutorDin FolclorAdăugată deioanabIoana Bica ioanab
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Rucsac fractionar

Se dau N obiecte pentru care se cunosc greutatea g si pretul p si un rucsac de capacitate K. Se cere sa se calculeze si sa se afiseze profitul maxim ce se poate obtine adaugand o submultime din cele N obiecte in rucsac. Se pot selecta si fractiuni ale obiectelor. Profitul este suma preturilor integrale la care se adauga fractiuni ale preturilor pentru obiectele selectate partial.

Date de intrare

Fişierul de intrare rucsacfr.in contine pe prima linie N si K cu semnificatia de enunt. Urmatoarele n linii contin 2 numere intregi separate printr-un spatiu, g si p, ce reprezinta greutatea si profitul fiecarui obiect.

Date de ieşire

În fişierul de ieşire rucsacfr.out se va afisa profitul maxim, cu o precizie de 2 zecimale.

Restricţii

  • 1 ≤ N ≤ 10.000
  • 1 ≤ K ≤ 1.000.000
  • Pretul si greutatea obiectelor au valori in intervalul [1, 1.000.000]

Exemplu

rucsacfr.inrucsacfr.out
6 7
1 7
5 19
4 5
2 5
3 14
1 1
32.40

Explicaţie

Pentru a obtine profitul maxim, se aleg obiectele 1, 2 si 5.

Trebuie sa te autentifici pentru a trimite solutii. Click aici