Fractional knapsack (zaino frazionario)
Dato
n oggetti con i rispettivi pesi e valori, si desidera inserire questi oggetti in uno zaino di capacità W in modo da ottenere il valore totale massimo possibile. È permesso prendere solo una frazione (parte) di un oggetto, e in tal caso il valore relativo viene ridimensionato proporzionalmente alla frazione scelta.Qual è il massimo valore totale che si può raggiungere nello zaino?
Input
La prima riga dell’input contiene due interi
n (1 ≤ n ≤ ), che indicano il numero di oggetti, e W (1 ≤ W ≤ ), la capacità dello zaino.Le successive
n righe contengono coppie di interi separate da uno spazio (1 ≤ , ≤ ), dove ciascuna coppia rappresenta il peso e il valore di un oggetto.Output
Il programma deve stampare il valore totale massimo ottenibile nello zaino.
Esempi
Ingresso | Uscita |
3 50
10 60
20 100
30 120 | 240 |
4 60
40 280
10 100
20 120
24 120 | 440 |
Spiegazione
- 60 + 100 + (2/3)120 = 240
- 280 + 100 + (10/20)120 = 440
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB