Mochila fraccionaria
Dado que tienes
n artículos con sus pesos y valores, deseas colocar esos artículos en una mochila de capacidad W para obtener el mayor valor total posible. Se te permite tomar una fracción (parte) de un artículo; en ese caso, el precio cambia proporcionalmente a la fracción que tomes.¿Cuál sería el valor total máximo que puede llevar la mochila?
Entrada
La primera línea de la entrada contiene dos enteros
n (1 ≤ n ≤ ), que representan el número de artículos, y W (1 ≤ W ≤ ), la capacidad de tu mochila.Las siguientes
n líneas contienen pares de enteros separados por espacio (1 ≤ , ≤ ) que indican el peso y el valor de cada artículo.Salida
El programa debe imprimir el valor total máximo que puede llevar la mochila.
Ejemplos
Entrada | Salida |
3 50
10 60
20 100
30 120 | 240 |
4 60
40 280
10 100
20 120
24 120 | 440 |
Explicación
- 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