Une question posée aux élèves de la spécialité NSI, et pour laquelle une petite mise en situation s’impose.

Durant un cambriolage, un voleur possède un sac dont la capacité en poids est limitée. Il se trouve face à un ensemble d’objets qu’il peut dérober. Chacun de ces objets est caractérisé par sa valeur et son poids.

Le voleur souhaite optimiser la valeur totale des objets qu’il va dérober tout en ne dépassant pas le poids maximal supporté par son sac.

Première méthode : le cambrioleur peut essayer toutes les possibilités et voir celle qui est optimale.

Avec 2 objets disponibles, il aura ainsi 4 tests à faire…

…et parmi ces 4 possibilités, il choisira celle qui respecte la contrainte de poids et pour laquelle la valeur totale est maximale .

Avec 3 objets, il aura 8 tests à faire :

On observe alors que pour n objets, 2n tests devraient être effectués. Ainsi, pour 50 objets (ce qui n’est pas énorme), on passe à environ…

… 100 000 000 000 000 tests !

Mieux vaut donc ne pas utiliser cette méthode… sauf si l’on a plusieurs années devant nous pour commettre notre méfait (ce qui est rarement le cas pour un cambrioleur).

D’où l’intérêt d’une deuxième méthode avec l’utilisation d’un algorithme, appelé algorithme glouton.

Cet algorithme, au programme de la spécialité NSI, prend en compte, en plus de la valeur et du poids de chaque objet, la valeur au poids. Le principe en est le suivant : on prend l’objet avec le plus grand poids au kilo, puis on complète en gardant la même stratégie, tant que le poids maximal autorisé n’est pas atteint.

A vous de jouer !

Animation crée par Ouest INSA, à partir de l’applet réalisée par Li Yifang.

Envie d’en savoir plus ?

Consulter cet article du site Interstices sur le problème du sac à dos.