====== Problème du sac à dos ======
===== Qu'est-ce ? =====
Il s'agit d'un problème classique d'algorithmique.
C'est le problème du **cambrioleur** : Le cambrioleur doit choisir rapidement quels objets il emporte. Il veut emporter un maximum de valeur mais il doit les mettre dans son sac dont la capacité est limitée.
Plus formellement :
* On dispose d'un sac de capacité C,
* d'un assortiment d'objets ayant tous un poids et une valeur.
* On cherche à placer des objets dans le sac en respectant la contrainte de capacité et en maximisant la valeur totale du contenu du sac.
**Exemple :** On dispose d'un sac d'une capacité de C = 15 kg et de la liste d'objets suivants :
^ Objet ^ Valeur ^ Poids ^
| A | 126 | 14 |
| B | 32 | 2 |
| C | 20 | 5 |
| D | 5 | 1 |
| E | 18 | 6 |
| F | 80 | 8 |
===== Algorithme glouton =====
L'algorithme glouton donne une réponse pas forcément optimale au problème posé mais il est simple :
- on trie le tableau selon un critère,
- on remplit le sac en prenant les objets dans l'ordre.
=== Valeur décroissante ===
Par exemple, trions le tableau par valeur décroissante.
^ Objet ^ Valeur ^ Poids ^
| A | 126 | 14 |
| F | 80 | 8 |
| B | 32 | 2 |
| C | 20 | 5 |
| E | 18 | 6 |
| D | 5 | 1 |
Puis complétons le sac en prenant, si possible, les objets dans l'ordre.
* On peut prendre A, ce qui occupe 14 kg de la capacité du sac,
* comme il ne reste que 1 kg de capacité, on ne peut pas prendre F, B, C, E.
* Enfin on peut prendre D.
Le sac contiendra A et D totalisant une valeur de 131.
=== Poids croissant ===
C'est un autre choix possible. Il aboutira à un contenu de sac différent.
^ Objet ^ Valeur ^ Poids ^
| D | 5 | 1 |
| B | 32 | 2 |
| C | 20 | 5 |
| E | 18 | 6 |
| F | 80 | 8 |
| A | 126 | 14 |
== Rapport valeur / poids décroissant ==
On peut aussi faire des calculs avec les attributs des objets. Par exemple, il semble raisonnable d'évaluer le rapport valeur / poids afin de choisir en priorité les objets qui apportent de la valeur sans trop encombrer le sac.
^ Objet ^ Valeur ^ Poids ^ rapport V/P ^
| B | 32 | 2 | 16 |
| F | 80 | 8 | 10 |
| A | 126 | 14 | 9 |
| D | 5 | 1 | 5 |
| C | 20 | 5 | 4 |
| E | 18 | 6 | 3 |
Là encore on obtient un sac différent.
> Remarquez qu'aucune de ces stratégies ne donne le meilleur sac, mais elles donnent de bons résultats.
===== Implémentation =====
=== Les objets ===
Les items disponibles seront représentés dans un dictionnaire. Par exemple :
objets = {
"A": { "valeur":126, "poids":14 },
"B": { "valeur":32, "poids":2 },
"C": { "valeur":20, "poids":5 },
"D": { "valeur":5, "poids":1 },
"E": { "valeur":18, "poids":6 },
"F": { "valeur":80, "poids":8 }
}
=== Sac ===
Le contenu du sac sera lui aussi représenté par un tableau. Par exemple :
sac = ["A", "D"]
=== fonctions utiles ===
Nous avons besoin des fonctions suivantes :
- trier les objets dans un ordre défini,
- calculer le poids total d'un sac,
- calculer la valeur d'un sac
- tester si on peut ajouter un objet dans un sac,
- ajouter un objet dans un sac
Voici un modèle **à compléter** puis **à exécuter** :
# sacados.py
# la dictionnaire objets contenant les objets sera une variable globale.
def tri(critere):
'''
critere: fonction qui pour nom d'objet donné renvoie sa valeur dans le tri
exemple : si on tri par valeur décroissante, critere(nom) doit renvoyer
la valeur de l'objet
la fonction renvoie un tableau avec les noms, par critère décroissant.
'''
return
def poids(sac):
'''
sac: tableau des noms des objets contenus dans le sac
renvoie la masse totale contenue dans le sac
'''
return 0
def valeur(sac):
'''
sac: tableau des noms des objets contenus dans le sac
renvoie la valeur totale de ce sac.
'''
return 0
def rentre_dans_le_sac(nom, sac, C):
'''
nom: nom de l'objet que l'on souhaite ajouter
sac: tableau des noms des objets contenus dans le sac
C: Capacité max du sac
renvoie True si l'objet peut entrer dans le sac, False sinon
'''
return False
def ajouter_objet_dans_sac(nom, sac):
'''
nom: nom de l'objet que l'on souhaite ajouter
sac: tableau des noms des objets contenus dans le sac
modifie sac en y ajoutant nom
'''
return
def glouton(C, critere):
'''
C: capacité max du sac
critere: fonction utilisée dans le tri
renvoie le sac obtenu par l'algorithme glouton suivant le critère défini
'''
return []
# démonstration
C = 15
objets = {
"A": { "valeur":126, "poids":14 },
"B": { "valeur":32, "poids":2 },
"C": { "valeur":20, "poids":5 },
"D": { "valeur":5, "poids":1 },
"E": { "valeur":18, "poids":6 },
"F": { "valeur":80, "poids":8 }
}
# exemple de critère
def critere_valeur(nom):
obj = objets[nom]
return obj["valeur"]
sac = glouton(C, critere_valeur)
print(sac)
print(valeur(sac))
=== Fonction lambda ===
En mathématique, une fonction consiste en l'association d'antécédents et d'images. On peut noter par exemple $x \mapsto 3x + 5$ l'idée que chaque nombre $x$ antécédent sera associer à l'image $3x+5$ : 0 est associé à 5 ; 1 est à 8 ; 2 est associé à 11 ; etc.
Notre fonction ''%%critere_valeur%%'' pourrait ainsi se noter $nom \mapsto objets[nom]['valeur']$. On comprendrait ce que fait cette fonction sans la définir avant et sans lui donner de nom, il suffit de savoir que l'antécédent est ''%%nom%%'' et que l'image est ''%%objets[nom]['valeur']%%''.
Il existe une notation pour cela en Python :
lambda nom: objets[nom]['valeur']
C'est une fonction anonyme prenant comme argument (//antécédent//) ''%%nom%%'' et renvoie (//image//) ''%%objets[nom]['Valeur']%%''.
Alors nous pouvons remplacer :
# code actuel
def critere_valeur(nom):
return objets[nom]['valeur']
sac = glouton(objets, critere_valeur)
# en utilisant lambda
sac = glouton(objets, lambda nom: objets[nom]['valeur'])
Le résultat est le même.
=== Autre critères ===
Exécutez le programme avec d'autres critères :
* rapport valeur / poids décroissant,
* poids croissant\\ //Il faut trouver une astuce puisque le tri se fait dans l'ordre décroissant du critère fourni !//
Essayez de le faire en utilisant ''%%lambda%%''.