Problème du sac à dos

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 :

L'algorithme glouton donne une réponse pas forcément optimale au problème posé mais il est simple :

1. on trie le tableau selon un critère,
2. on remplit le sac en prenant les objets dans l'ordre.

Par exemple, trions le tableau par valeur décroissante.

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.

C'est un autre choix possible. Il aboutira à un contenu de sac différent.

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.

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.

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 }
}

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

sac = ["A", "D"]

Nous avons besoin des fonctions suivantes :

1. trier les objets dans un ordre défini,
2. calculer le poids total d'un sac,
3. calculer la valeur d'un sac
4. tester si on peut ajouter un objet dans un sac,
5. 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))

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.

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.