| Fișierul intrare/ieșire: | rucsacfr.in, rucsacfr.out | Sursă | ad-hoc |
| Autor | din folclor | Adăugată de |  Ioana Bica •ioanab |
| Timp execuție pe test | 0.1 sec | Limită de memorie | 65536 KB |
| Scorul tău | N/A | Dificultate |   1/5 |
Poți vedea testele pentru această problemă accesând atașamentele.Vezi soluțiile 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.
