Fractional knapsack
Gegeben sind
n Gegenstände mit ihrem jeweiligen Gewicht und Wert. Diese sollen in einen Rucksack mit Kapazität W gepackt werden, sodass der Gesamtwert im Rucksack maximiert wird. Dabei ist es erlaubt, einen beliebigen Bruchteil (Teil) eines Gegenstands zu nehmen; in diesem Fall ändert sich der Wert proportional zu dem genommenen Bruchteil.Wie lässt sich der maximale Gesamtwert für den Rucksack bestimmen?
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n (1 ≤ n ≤ ), die Anzahl der Gegenstände, und W (1 ≤ W ≤ ), die Kapazität des Rucksacks.Die folgenden
n Zeilen enthalten jeweils zwei ganzzahlige Werte (1 ≤ , ≤ ), die das Gewicht und den Wert des jeweiligen Gegenstands angeben.Ausgabe
Das Programm soll den maximalen Gesamtwert ausgeben, der in den Rucksack passt.
Beispiele
Input | Output |
3 50
10 60
20 100
30 120 | 240 |
4 60
40 280
10 100
20 120
24 120 | 440 |
Erklärung
- 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