S. 2. Nous avons trouvé une grotte à trésor qui contient n trésors de masses et de valeurs différentes. De ces trésors, nous aimerions mettre quelques-uns dans notre sac à dos de charge maximale w kg, de façon à avoir un trésor de valeur maximale.

Ecrire un programme calculant la valeur maximale qu'on peut emporter. La première ligne de l'entrée du programme contiendra n, la deuxième ligne w. Les n lignes suivantes contiennent la masse et la valeur d'un des n trésors. ( ces données sont considérées comme correctes, on ne demande pas le contrôle ) La sortie du programme sera un seul nombre, la valeur maximale à emporter.

Exemple :

A renvoyer : Le programme, sa brève description, le résultat d'exécution sur les données de test. Ne renvoyer que les programmes qui ont des résultats corrects sur les tests donnés avec résultat ci-dessous.

Correction : Vous pouvez obtenir des points si votre programme correspond à l'énoncé, il peut être compilé, il est bien commenté et il donne le bon résultat sur les données des petits tests. (max. 5 points). Vous pouvez obtenir 3 points de plus si le programme produit les bons résultats sur les données des grands tests (10 minutes de temps d'exécution max. ). Si le programme donne les bons résultats sur les données des tests géants (en 1 heure max.), on donne 1 point extra pour chacun de ces tests.

Données de tests

(10 points)