Il s'agit d'un problème classique permettant pour lequel une recherche systématique mal construite risquerait de demander trop de temps. Pour ce problème, l'algorithme glouton donne de bons résultats.
C'est le problème du cambrioleur. Son sac est de taille limitée et il cherche à emporter le plus de valeurs possibles.
On dispose de $n$ objets qui ont chacun un poids $p_i$ et une valeur $v_i$ pour $i$ dans $[[0, n-1]]$ et d'un sac qui peut supporter un poids maximal $P$ . Quels objets faut-il prendre pour optimiser le remplissage du sac à dos du point de vue de la valeur transportée ?
Un problème d'optimisation est un problème dans lequel on cherche à maximiser un gain – ou minimiser une dépense – tout en respectant une contrainte. Dans le problème du sac à dos, s'il n'y avait pas la contrainte de la capacité maximale du sac, il suffirait de prendre tout ce qu'il y a à prendre. C'est bien parce qu'il y a la contrainte que l'on doit choisir, et pour choisir il nous faut un critère de choix. Notre critère de choix est de rechercher la valeur maximale.
Pour un $n$ petit, la force brute donne un résultat rapidement : pour $n$ objets, il y a $2^n$ choix de sacs possibles. Par exemple, si $n = 10$, on a $2^n = 1024$, on peut envisager de les essayer tous. Mais si $n = 100$, $2^n \simeq 1E30$, on ne pourra les essayer tous !
Le principe d'une stratégie par algorithme glouton est de trier les items dans un certain ordre et de les faire entrer dans le sac dans cet ordre.
Mais quel ordre choisir ?
Ces trois choix sont valables. On n'a aucune garantie de trouver la meilleure solution quelque soit l'ordre choisi. On trouvera seulement une bonne solution.
À titre d'exemple, supposons qu'on ait la liste d'objet
| indice | nom | poids | valeur |
|---|---|---|---|
| 0 | collier | 1 | 600 |
| 1 | écran | 10 | 200 |
| 2 | globe | 7 | 120 |
| 3 | lampe | 5 | 40 |
| 4 | fleur | 4 | 10 |
| 5 | écrin | 2 | 300 |
| 6 | coffre | 25 | 1500 |
| 7 | livre | 5 | 30 |
| 8 | caisse | 12 | 100 |
| 9 | enclume | 20 | 20 |
| 10 | statuette | 6 | 250 |
| 11 | livre rare | 5 | 220 |
Dans le programme on disposera d'une liste ayant cette forme :
liste = [
{"nom":"collier", "poids":1, "valeur":600},
{"nom":"écran", "poids":10, "valeur":200},
{"nom":"globe", "poids":7, "valeur":120},
{"nom":"lampe", "poids":5, "valeur":40},
{"nom":"fleur", "poids":4, "valeur":10},
{"nom":"écrin", "poids":3, "valeur":300},
{"nom":"coffre", "poids":25, "valeur":1500},
{"nom":"livre", "poids":5, "valeur":30},
{"nom":"caisse", "poids":12, "valeur":100},
{"nom":"enclume", "poids":20, "valeur":20},
{"nom":"statuette", "poids":6, "valeur":250},
{"nom":"livre rare", "poids":5, "valeur":220}
]
Les items du tableau, il faut préciser par rapport à quelle mesure on doit les ordonner. On doit donc indiquer au tri une fonction $item \mapsto evaluation$.
Par exemple si on veut trier par valeur croissante, il nous faut : $item \mapsto valeur(item)$. On peut définir cette fonction de façon classique :
def critere_valeur(item):
return item["valeur"]
Puis le tri sera :
liste.sort(key = critere_tri)
et si on veut un ordre décroissant, il suffit de le préciser :
liste.sort(key = critere_tri, reverse = True)
On peut aussi (ce sera mieux ici) modifier le critère : si on veut trier par valeur décroissante, il suffit de choisir :
def critere_valeur(item):
return -item["valeur"]
Le - change naturellement l'ordre de sorte que liste.sort(key = critere_tri) triera par valeur décroissante.
FONCTION sac_a_dos
ENTRÉES
liste: tableau contant la liste des objets avec leur nom, poids et valeur
P: poids maximum que peut emporter le sac
critere: la fonction définissant le critère de tri
SORTIE
un tuple contenant :
la liste des noms,
le poids du sac,
la valeur du sac
DÉBUT
initialiser contenu à vide, poids et valeur à 0
trier la liste suivant le critère retenu
POUR CHAQUE item DE liste FAIRE
SI le sac a assez de place pour cet item ALORS
ajouter le nom de cet item au contenu
ajouter le poids et la valeur de cet item à poids et valeur
FIN
FIN
RENVOYER contenu, poids, valeur
P = 20.