Fişierul intrare/ieşire: | rucsacfr.in, rucsacfr.out | Sursă | ad-hoc |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 0.1 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
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.in | rucsacfr.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.