Sac à dos fractionnaire
Supposons que vous disposiez de n objets, chacun ayant un poids et une valeur. Votre objectif est de les placer dans un sac à dos d’une capacité W, afin de maximiser la valeur totale que vous pouvez y mettre. Vous avez le choix de ne prendre qu’une partie (fraction) de chaque objet, auquel cas la valeur associée variera proportionnellement à cette fraction.
Quelle est alors la valeur totale maximale que le sac à dos peut contenir ?
Entrée
La première ligne de l’entrée contient deux entiers n (1 ≤ n ≤ ), le nombre d’objets, et W (1 ≤ W ≤ ), représentant la capacité de votre sac à dos.
Les n lignes suivantes contiennent chacune deux entiers séparés par un espace, (1 ≤ , ≤ ), correspondant respectivement au poids et à la valeur de chaque objet.
Sortie
Le programme doit afficher la valeur totale maximale que peut contenir le sac à dos.
Exemples
Entrée | Sortie |
|---|---|
3 50 | 240 |
4 60 | 440 |
Explication
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