Il s'agit d'un problème classique d'algorithmique.

• 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. puis 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 par des dictionnaires dans un tableau. Par exemple :

objets = [
  { "Nom":"A", "Valeur":126, "Poids":14 },
  { "Nom":"B", "Valeur":32, "Poids":2 },
  { "Nom":"C", "Valeur":20, "Poids":5 },
  { "Nom":"D", "Valeur":5, "Poids":1 },
  { "Nom":"E", "Valeur":18, "Poids":6 },
  { "Nom":"F", "Valeur":80, "Poids":8 }
]

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

sac = [
  { "Nom":"A", "Valeur":126, "Poids":14 },
  { "Nom":"D", "Valeur":5, "Poids":1 }
]

Nous avons besoin des fonctions suivantes :

1. ajouter un objet dans un sac si c'est possible,
2. trier les objets dans un ordre défini,
3. calculer la valeur d'un sac

Voici un modèle à compléter puis à exécuter :

sacados.py

'''
Algorithme glouton : problème du sac à dos
'''
 
def poids_sac(sac):
    '''
    sac: sac dont on veut la masse du contenu
    renvoie la masse totale contenue dans le sac
    '''
    return 0
 
def ajouter_objet_dans_sac(C, sac, objet):
    '''
    C: Capacité max du sac
    sac: sac dans lequel mettre l'objet
    objet: objet à mettre dans le sac
    ajoute l'objet dans le sac si c'est possible.
    renvoie True en cas de succès, False sinon
    '''
    return False
 
def tri(objets, critere):
    '''
    objets: tableau des objets disponibles à trier
    critere: fonction qui pour un un objet donné renvoie sa valeur dans le tri
      exemple : si on tri par valeur décroissante, critere(objet) doit renvoyer la valeur de l'objet
    trie les objets selon le critère, toujours par ordre décroissant
    ne renvoie rien, trie objets en place
    '''
    return
 
def valeur_sac(sac):
    '''
    sac: sac dont on veut la valeur
    renvoie la valeur totale de ce sac.
    '''
    return 0
 
def glouton(objets, C, critere):
    '''
    objets: tableau des objets que l'on peut mettre dans le sac
    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 []
 
if __name__ == '__main__':
    # tests
    C = 15
    objets = [
      { "Nom":"A", "Valeur":126, "Poids":14 },
      { "Nom":"B", "Valeur":32, "Poids":2 },
      { "Nom":"C", "Valeur":20, "Poids":5 },
      { "Nom":"D", "Valeur":5, "Poids":1 },
      { "Nom":"E", "Valeur":18, "Poids":6 },
      { "Nom":"F", "Valeur":80, "Poids":8 }
    ]
 
    def critere_valeur(objet):
        return objet["Valeur"]
 
    sac = glouton(objets, critere_valeur)
    print(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 $objet \mapsto objet[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 objet et que l'image est objet["Valeur"].

Il existe une notation pour cela en Python :

lambda objet: objet["Valeur"]

C'est une fonction anonyme prenant comme argument (antécédent) objet et renvoie (image) objet["Valeur"].

Alors nous pouvons remplacer :

# code actuel, dans les tests
def critere_valeur(objet):
    return objet["Valeur"]
sac = glouton(objets, critere_valeur)

# en utilisant lambda
sac = glouton(objets, lambda objet: objet["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.