Corrigés de l'exercice 9.6

Question 9.6.1

Pour amasser le plus gros butin, il suffit de considérer les différentes substances en commençant par la plus chère. A chaque fois, on en prend la quantité maximale (soit en prenant toute la quantité disponible, soit en finissant de remplir le sac).

Programme Python

Question 9.6.2

L’algorithme proposé pour la question 1 ne peut pas s’étendre. Par exemple, si on peut porter 3 kilos et qu’il y a un objet de 3 kilos de valeur 3 et deux objets de 1 kilo de valeur 2, l’algorithme dit de prendre l’objet de 3 kilos alors qu’on peut amasser un meilleur butin en prenant les deux objets de 1 kilo.

Didier Müller, 19.7.09