Le problème du sac à dos

Introduction

Ce problème est une abstraction pour un grand nombre d’autres problèmes d’optimisation. Il a été utilisé en cryptographie comme base pour différents schémas de chiffrement1. Il faut cependant noter que la plupart de ces schémas de chiffrement ne sont plus actuellement considérés comme sûrs. ^1, il est utilisé lors du chargement des bateaux ou d’avions, lors de la découpe de matériaux (minimisation des coupes « chutes » lors de la découpe), etc.

Problème étudié

On considère un sac à dos de masse maximale $m = \pu{40 kg}$ dans lequel on souhaite ranger les objets dont les caractéristiques sont données ci-dessous :

Quels objets faut-il sélectionner de façon à ce que la valeur totale, dans le sac à dos, soit maximale ?

Méthode de résolution approchée : stratégie gloutonne

1. Rappeler ce qu’est une stratégie gloutonne.

2. Dans la partie principale du programme, définir la liste objets dont les membres sont des dictionnaires représentant les différents objets du problème.
   Chacun de ces dictionnaires doit posséder les clés nom, masse, valeur associées aux valeurs.

1
2
3
4
5
6
7
8

if __name__ == "__main__":
    objets = [{'nom': 'A', 'masse': 13, 'valeur': 700},
                {'nom': 'B', 'masse': 12, 'valeur': 500},
                {'nom': 'C', 'masse': 8, 'valeur': 200},
                {'nom': 'D', 'masse': 10, 'valeur': 300},
                {'nom': 'E', 'masse': 14, 'valeur': 600},
                {'nom': 'F', 'masse': 18, 'valeur': 800}
                ]

3. Définir la variable masse_max et lui affecter la valeur 40.

1

masse_max = 40

Le principe de la stratégie gloutonne consiste à ajouter en priorité les objets « les plus efficaces ». « Plus efficace » ne signifie pas « plus grande valeur » mais « plus grande valeur comparativement à la masse ».

Avant d’appliquer l’algorithme glouton, il est nécessaire de trier la liste objets. Définir la fonction suivante :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def tri_objets(objets: list[dict]) -> list[dict]:
    """
    Trie la liste de dictionnaires selon les rapports valeur/masse.
    """
    def recupere_rapports(objet):
        return objet['valeur'] / objet['masse']

    objets_tries = sorted(objets, key=recupere_rapports)

    return objets_tries

4. Quel concept propre à la programmation fonctionnelle la fonction sorted met-elle en œuvre ?

5. Décrire précisément la structure et le comportement de la fonction tri_objets.

6. Affecter, dans la fonction main, le résultat de l’appel de la fonction tri_objets à la variable objets.
   Afficher à l’écran la liste triée.

1
2

objets = tri_objets(objets)
print(f"Objets utilisables : {objets}", end='\n')

Remarque.

Ne pas oublier d’appeler la fonction main.

7. Définir la fonction construction_sac_a_dos dont la spécification est :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def constrution_sac_a_dos(objets_tries: list[dict], 
                          masse_max: float) -> tuple[list[str], int, int]:
    """
    Construction du sac à dos à partir d'une stratégie gloutonne.
    HYPOTHÈSE : la liste de dictionnaires est triée par ordre croissant des rapports
    valeurs/masses.

    Retourne un tuple constitué d'une liste contenant les noms des objets sélectionnés, 
    de la valeur du sac à dos et de la masse du sac à dos.
    """

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def constrution_sac_a_dos(objets_tries: list[dict], masse_max: float) -> tuple[list[str], int, int]:
    """
    Construction du sac à dos à partir d'une stratégie gloultonne.
    HYPOTHÈSE : la liste de dictionnaires est triée par ordre croissant des rapports
    valeurs/masses.

    Retourne un tuple constitué d'une liste contenant les noms des objets sélectionnés, 
    de la valeur du sac à dos et de la masse du sac à dos.
    """
    masse_sac = 0
    valeur = 0
    liste_objets = []

    i = len(objets_tries) - 1  # Compteur
    while i >= 0:
        objet = objets_tries[i]  # objet est un dictionnaire
        if (masse_sac + objet['masse']) <= masse_max:
            valeur += objet['valeur']
            masse_sac += objet['masse']
            liste_objets.append(objet['nom'])
    
        i -= 1  # Décrémentation du compteur

    return (liste_objets, valeur, masse_sac)

8. Affecter, dans la partie principale du programme, le tuple retourné par la fonction construction_sac_a_dos aux variables sac_a_dos,valeur et masse_sac.

1

sac_a_dos, valeur, masse_sac = constrution_sac_a_dos(objets, masse_max)

9. Afficher le résultat :

1
2
3
4
5
6

print("Stratégie gloutonne")
print("-------------------")
print(f"Constitution du sac à dos : {sac_a_dos}")
print(f"Masse du sac à dos : {masse_sac}")
print(f"Valeur du sac à dos : {valeur}")
print()

Extension : Méthode de résolution exacte

Si on ne prend pas en compte, dans un premier temps, les contraintes, il est possible d’établir la liste des combinaisons possibles des objets à l’aide d’un arbre d’exploration binaire.

Par exemple, voici ce à quoi cet arbre ressemble lorsqu’on prend en compte les trois premiers objets :

graph TD
V("" ) --- A
V --- V1((" "))
A --- C(("A,B"))
C --- D(("A,B,C"))
C --- E(("A,B"))
A --- F(("A"))
F --- G(("A,C"))
F --- H(("A"))
V1 --- I(("B"))
I --- J(("B,C"))
I --- K(("B"))
V1 --- V2((" "))
V2 --- L(("C"))
V2 --- M((" "))

Les combinaisons s’obtiennent en parcourant l’arbre du sommet jusqu’à chaque extrémité : on obtient alors un vecteur dont on peut calculer la poids et la valeur. Il suffit alors de retenir celui dont la masse est inférieure à la masse maximale et dont la valeur est alors maximale.

10. Au niveau de chaque nœud à quoi correspond le chemin « gauche » : objet retenu ou objet non retenu ?

11. Compléter l’arbre avec l’objet D.

12. Si on implémente un algorithme mettant en œuvre la technique présentée ici, on trouve comme solution $[A,C,F]$. Vérifier que cette solution est meilleure que celle donnée par l’algorithme glouton.
    Pourquoi cette méthode n’est cependant pas utilisable la plupart du temps ? Quel est le nombre de combinaisons possibles ?

13. Écrire le code de la fonction masse_sac dont la spécification est :

1
2
3
4

def masse_sac(objets: list[dict[str, str]], liste_obj: list[int]) -> int:
    """
    Calcule la masse du sac pour la liste d'objets retenus liste_obj.
    """

14. Écrire le code de la fonction calcul_valeur_sac dont la spécification est :

1
2
3
4
5

def calcul_valeur_sac(objets: list[dict[str, str]],
                      liste_obj: list[int]) -> int:
    """
    Calcule la masse du sac pour la liste d'objets retenus liste_obj.
    """

15. Écrire le code suivant :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def recherche_recursive(objets: list[dict[str, str]], masse_max: isinstance,
                        list_obj: list[int], i: int) -> list[int]:
    """
    Détermine le chemin de l'arbre de décision correspondant à la valeur optimale
    pour une masse du sac déterminée.
    """
    if i == len(objets):
        return list_obj[:]

    val1 = -1  # Initialisation à une valeur impossible du poids
    if objets[i]['masse'] <= masse_max - masse_sac(
            objets, list_obj):  # Ajoute objet si m_sac - m_inter > 0
        list_obj[i] = 1
        sol1 = recherche_recursive(objets, masse_max, list_obj, i + 1)
        val1 = calcul_valeur_sac(objets, sol1)

    list_obj[i] = 0  # On n'ajoute pas l'objet
    sol2 = recherche_recursive(objets, masse_max, list_obj, i + 1)
    val2 = calcul_valeur_sac(objets, sol2)

    if val1 > val2:
        return sol1[:]
    else:
        return sol2[:]

Examiner cette fonction

Suggestions de lecture :

• Arbres Binaires Recherche
• Les arbres binaires
• Structures de données abstraites arborescentes : les arbres