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
10 60
20 100
30 120 | 240 |
4 60
40 280
10 100
20 120
24 120 | 440 |
Explication
- 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