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 ?

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 ?

• Les plus légers en premiers ?
• Les plus hautes valeurs en premiers ?
• Ceux qui ont le meilleur rapport valeur/poids en premier ?

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

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.

1. On a besoin de trier le tableau suivant un certain critère. Définissez une fonction critère pour les 3 cas :
   • par valeur décroissante,
   • par poids croissant,
   • par rapport valeur/poids décroissante.
2. Voici l'algorithme glouton pour le sac à dos :

   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
   

3. Testez la fonction avec les 3 critères en prenant P = 20.
4. Comme dans ce cas le tableau est de petite taille, cherchez le meilleur sac en force brute (c'est à dire en essayant tous les cas) et comparez avec la réponse obtenue avec l'algorithme glouton.
5. comparez la complexité de la recherche brute avec la complexité de l'algorithme glouton.