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

• On dispose d'un sac de capacité C en kg,
• 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 :

sacados.py

'''
Algorithme glouton : problème du sac à dos
'''
 
def ajouter_objet_dans_sac(sac, objet):
    '''
    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_sac(sac, critere):
    '''
    sac: sac à 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 le sac selon le critère, toujours par ordre décroissant
    '''
    return
 
def valeur_sac(sac):
    '''
    sac: sac dont on veut la valeur
    renvoie la valeur totale de ce sac.
    '''
    return 0
 
def glouton(objets, critere):
    '''
    objets: tableau des objets que l'on peut mettre dans le 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
    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_poids(objet):
        return objet["Poids"]
 
    sac = glouton(objets, critere_poids)
    print(sac)