Fișierul intrare/ieșire: rucsacfr.in, rucsacfr.out Sursă ad-hoc
Autor din folclor Adăugată de ioanabIoana Bica ioanab
Timp execuție pe test 0.1 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate normalnormalnormalnormalnormal

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.

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

Indicii de rezolvare

Arată 1 categorie