Exercice

Voici le problème du sac à dos : nous avons un sac à dos pouvant supporter un poids maximum, nous possédons une série d'objet ayant chacun un poids. Le problème à résoudre est alors : quels objets choisir pour transporter le sac le plus lourd possible sans dépasser son maximum ?.

Dans l'exemple ci-dessous, le poids maximal que peut supporter le sac est 15 kg.

Le problème du sac à dosInformations[1]

Question

Dans le cas de l'exemple ci-dessus, quels objets faudrait-il prendre pour avoir le sac le plus lourd possible sans dépasser 15 kg ?

Indice

Il y a deux solutions possibles.

Solution

Il faut prendre soit les objets vert, rouge et bleu soit les vert, gris et bleu. Dans les deux cas, on atteint 15 kg.

Question

Quel est la classe de ce problème ?

Indice

Pour résoudre ce problème, il faut tester toutes les combinaisons d'objets une à une. Une fois toutes les combinaisons calculées il faudra conserver celle qui permet d'atteindre le poids le plus haut sans dépasser le poids maximum supporté par le sac.

Indice

Imaginer que nous ayons pas 5 objets possibles mais 10, 20, 100 ou même 1000. La croissance du nombre de possibilités à vérifier serait-elle exponentielle ?

Solution

C'est un problème NP. En effet, le temps pour résoudre sera exponentiel en fonction du nombre de poids. Pour résoudre ce problème, il faut calculer le poids de toutes les combinaisons possibles d'objets. Or, le nombre de combinaisons est exponentiel en fonction du nombre d'objets.