Le problème du sac à dos
Supposons que vous souhaitiez emporter des objets ayant chacun une certaine valeur mais que vous n'ayez à votre disposition qu'un sac ne pouvant supporter que 15 kg maximum. Quels objets faut-il emmener pour que la valeur du sac soit maximale ?
En vérité, ceci s'étant à des problématiques plus "concrètes", comme la finance, le chargement d'un cargo, etc. mais restons sur le sac à dos.
Sac à dos, méthode naïve (ou exhaustive)⚓︎
Une première méthode consiste à lister toutes les combinaisons possibles d'objets puis de regarder lesquelles ne dépassent pas 15 kg et enfin de regarder laquelle permet d'avoir une somme maximale.
Combien y a-t-il de telles combinaisons ?
Considérons chaque objet : nous pouvons soit le prendre, soit le laisser donc il y a 2 choix. S'il y a 5 objets, cela donne donc 25 = 32 combinaisons possibles à examiner, ce qui reste raisonnable.
Par contre, avec 100 objets, il y aura 2100 = 1267650600228229401496703205376 combinaisons, ce qui est nettement moins gérable.
Le coût de la méthode naïve est donc en O(2n), c'est un coût exponentiel.
Sac à dos, méthode glouton⚓︎
Si l'on ne veut pas passer trop de temps pour remplir son sac à dos, il va falloir trouver une autre méthode !
Dans tous les cas, nous pouvons considérer que nous allons mettre un seul objet à la fois dans le sac. Un algorithme glouton consiste à faire le meilleur choix possible pour chaque objet, sans s'occuper de la suite et sans possibilité de revenir en arrière.
Ok, mais c'est quoi le meilleur choix ?
Exercice 1
Voici cinq objets, leur poids et leur valeur. Vous disposez d'un sac de capacité maximale de 32 kg.
| Objet | Poids (kg) | Valeur (euros) |
|---|---|---|
| A | 16 | 512 |
| B | 15 | 495 |
| C | 19 | 950 |
| D | 14 | 280 |
| E | 14 | 420 |
- Choisissons un critère de choix d'un objet à mettre dans le sac : il faut qu'il ait le plus petit poids (sans dépasser la capacité restante bien sûr). Quelle est la valeur du sac si on applique ce critère à chaque choix d'un objet ?
- Définissez un autre critère de choix. Appliquez-le à chaque choix d'objet et donnez la valeur ainsi obtenue.
- Mêmes questions avec un troisième critère de choix.
- Y a-t-il une meilleure valeur totale que celles obtenues dans les trois questions précédentes ?
Remarques
- en fonction des valeurs, certains critères de choix fonctionneront mieux que d'autres ; ainsi le choix d'un ratio valeur/poids maximal semble le plus pertinent (et le sera la plupart du temps) ;
- dans les trois premières questions, nous avons utilisé une méthode gloutonne et nous voyons que celles-ci ne donnent pas forcément la réponse optimale. En ce sens, une méthode gloutonne est une heuristique, c'est-à-dire une méthode qui permet de trouver une solution convenable mais non forcément optimale à un problème mais en un temps raisonnable en évitant une analyse complète de ce problème.
- la programmation dynamique, étudiée en Terminale, est une technique appliquable ici.
Algorithme glouton
Type d'algorithme dans lequel, à chaque étape, un choix optimal local est fait, sans tenir compte de la suite et sans possibilité de retour en arrière (pensez à un glouton qui avale un objet, impossible de revenir en arrière...).
Comparez donc :
- la méthode exhaustive (étude de tous les cas ou force brute) : permet de trouver la meilleure solution à un problème mais en un temps qui peut être considérable ;
- une méthode gloutonne : ne donne pas forcément la solution optimale à un problème mais donne souvent une solution acceptable en un temps limité.
Par exemple, lors du chargement d'un cargo, vaut-il mieux tester toutes les combinaisons et bloquer le cargo pendant une semaine ou avoir une cargaison de valeur un peu inférieure à la cargaison optimale... ?
Problème
Il arrive parfois qu'une méthode gloutonne ne donne pas de solution du tout, comme nous le verrons ensuite.