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.
====== 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 :
<Code python>
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 }
}
</Code> 

=== Sac ===

Le contenu du sac sera lui aussi représenté par un tableau. Par exemple :

<Code python>
sac = ["A", "D"]
</Code>

=== 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** :

<code python>
# 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))
</code>

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

<code python>
lambda nom: objets[nom]['valeur']
</code>

C'est une fonction anonyme prenant comme argument (//antécédent//) ''%%nom%%'' et renvoie (//image//) ''%%objets[nom]['Valeur']%%''.

Alors nous pouvons remplacer :
<code python>
# 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']) 
</code>

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%%''.