Algorithmes gloutons
Les algorithmes gloutons forment un ensemble de méthodes très répandu qui construit la solution finale progressivement, en choisissant systématiquement la solution la plus évidente ou la plus optimale à chaque étape. Ils sont en général assez simples, mais il peut parfois être complexe de déterminer la bonne stratégie à appliquer à chaque phase.
Défi
Vous disposez d’un sac à dos et de
n objets. Vous souhaitez emporter autant d’objets que possible, mais vous savez que le sac peut se déchirer si la charge est trop lourde (si le poids total dépasse la limite t). Vous voulez donc déterminer le nombre maximal d’objets que vous pouvez mettre dans votre sac tout en restant dans la limite de poids.Entrée
La première ligne de l’entrée contient deux entiers
n (1 ≤ n ≤ ) et t (1 ≤ t ≤ ) – le nombre d’objets et la capacité maximale du sac à dos.La ligne suivante contient
n entiers séparés par des espaces (1 ≤ ≤ ) – les poids de chacun des objets.Sortie
Le programme doit afficher le nombre maximal d’objets que vous pouvez emporter.
Exemples
Entrée | Sortie |
7 10
4 1 2 5 8 7 1 | 4 |
Explication
Il est possible de transporter
1, 2, 5, 1, ou 4, 1, 2, 1, ou encore 1, 2, 7, 1. Dans chacun de ces cas, on obtient un total de 4 objets.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB