Дробный рюкзак (Fractional knapsack)
У вас есть
n предметов, для каждого из которых заданы вес и ценность. Вы хотите положить эти предметы в рюкзак вместимостью W, чтобы получить максимально возможную суммарную ценность. При этом можно взять лишь часть (долю) какого-то предмета, и тогда его ценность изменится пропорционально взятой части.Какова будет максимальная суммарная ценность рюкзака?
Входные данные
Первая строка входа содержит два целых числа
n (1 ≤ n ≤ ) — количество предметов и W (1 ≤ W ≤ ) — вместимость вашего рюкзака.Следующие
n строк состоят из пар целых чисел (1 ≤ , ≤ ), которые обозначают вес и ценность каждого предмета.Выходные данные
Программа должна вывести максимально возможную суммарную ценность рюкзака.
Примеры
Вход | Выход |
3 50
10 60
20 100
30 120 | 240 |
4 60
40 280
10 100
20 120
24 120 | 440 |
Пояснение
- 60 + 100 + (2/3)120 = 240
- 280 + 100 + (10/20)120 = 440
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB