Mochila fracionária
Dado
n itens com seus pesos e valores, você deseja colocá-los em uma mochila com capacidade W para obter o máximo valor total. É possível levar apenas uma fração (parte) de um item, e nesse caso o valor muda proporcionalmente à fração que foi levada.Qual seria o valor total máximo que podemos alcançar na mochila?
Entrada
A primeira linha da entrada contém dois inteiros
n (1 ≤ n ≤ ), o número de itens, e W (1 ≤ W ≤ ), a capacidade da mochila.As próximas
n linhas contêm pares de inteiros separados por espaço (1 ≤ , ≤ ), que representam o peso e o valor de cada item.Saída
O programa deve imprimir o valor total máximo que pode ser obtido na mochila.
Exemplos
Entrada | Saída |
3 50
10 60
20 100
30 120 | 240 |
4 60
40 280
10 100
20 120
24 120 | 440 |
Explicação
- 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