GoupillWiki

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Sac à dos ======

===== Présentation =====

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 ?

<WRAP info>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.</WRAP>

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 !

===== Stratégie gloutonne =====

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.

===== La liste d'objets =====

À 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 :

<code python>
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}
]
</code>

===== Rappel sur le tri =====

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 :

<code python>
def critere_valeur(item):
    return item["valeur"]
</code>

Puis le tri sera :

<code python>
liste.sort(key = critere_tri)
</code>

et si on veut un ordre décroissant, il suffit de le préciser :

<code python>
liste.sort(key = critere_tri, reverse = True)
</code>

On peut aussi (ce sera mieux ici) modifier le critère : si on veut trier par valeur décroissante, il suffit de choisir :

<code python>
def critere_valeur(item):
    return -item["valeur"]
</code>

Le ''-'' change naturellement l'ordre de sorte que ''liste.sort(key = critere_tri)'' triera par valeur décroissante.

===== Implémentation =====

  - 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.
  - Voici l'algorithme glouton pour le sac à dos :<code lang-none>
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
</code>
  - Testez la fonction avec les 3 critères en prenant ''P = 20''.
  - 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.
  - comparez la complexité de la recherche brute avec la complexité de l'algorithme glouton.