{"cells":[{"metadata":{"trusted":false},"cell_type":"markdown","source":"

TP n°23 : Le problème du sac à dos

"},{"metadata":{},"cell_type":"markdown","source":"
\nEn algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire. Ce problème classique en informatique et en mathématiques modélise une situation analogue au remplissage d'un sac à dos. Il consiste à trouver la combinaison d'éléments la plus précieuse à inclure dans un sac à dos, étant donné un ensemble d'éléments décrits par leurs masses et valeurs.\n\nL'objectif du problème du sac à dos est de sélectionner des objets à mettre dans le sac à dos de façon à maximiser la somme des valeurs des objets pris, sous la contrainte que la masse totale des objets pris ne dépasse pas la capacité du sac à dos. Ce problème est difficile à résoudre, en particulier pour les grands ensembles d'objets.\n\nPour résoudre le problème du sac à dos, il existe plusieurs algorithmes et approches différentes, notamment la programmation dynamique, les algorithmes gloutons et la programmation en nombres entiers. Ces algorithmes peuvent être appliqués à un large éventail de problèmes réels, tels que préparer une valise pour un voyage, allouer des ressources dans une chaîne d'approvisionnement et optimiser la gestion des stocks.
\n\n\"Sac\n\nSource : [Wikipedia](https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos)\n
"},{"metadata":{},"cell_type":"markdown","source":"#
⚠ Pensez à sauvegarder régulièrement votre travail (cliquez sur le bouton qui clignote en bleu en haut à gauche) ⚠
"},{"metadata":{},"cell_type":"markdown","source":"# 1. Présentation du problème\n
\nOn dispose d’un sac pouvant supporter une masse maximale donnée et de divers objets ayant chacun une valeur et une masse. Il s’agit de choisir les objets à emporter dans le sac afin d’obtenir la valeur totale la plus grande tout en respectant la contrainte de masse maximale. C’est un problème d’*optimisation avec contrainte*.\n\nCe problème peut se résoudre par force brute, c’est-à-dire en testant tous les cas possibles. Mais ce type de résolution présente un problème d’efficacité. Son coût en fonction du nombre d’objets disponibles croît de manière exponentielle.\n\nNous pouvons aussi envisager une stratégie gloutonne. Le principe d’un algorithme glouton est de faire le meilleur choix pour prendre le premier objet, puis le meilleur choix pour prendre le deuxième, et ainsi de suite. Que faut-il entendre par meilleur choix ? Est-ce prendre l’objet qui a la plus grande valeur, l’objet qui a la plus petite masse, l’objet qui a le rapport valeur/masse le plus grand ? Cela reste à définir.\n***\n**Le problème à résoudre :**\n\nOn doit choisir parmi 7 objets, dont les valeurs et masses sont indiquées dans le tableau ci-dessous, lesquels nous pouvons mettre dans un sac à dos de capacité maximale 10 kg. On place dans le son sac à dos les objets dont le rapport valeur/masse est le plus grand possible tout en ne dépassant pas la capacité maximale (masse maximale) du sac à dos.\n\n| Objet | A | B | C | D | E | F | G |\n| :------------ |:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Valeur (en €) | 10 | 11 | 23 | 9 | 30 | 6 | 8 |\n| Masse (en kg) | 2 | 4,5 | 5 | 4 | 9 | 1 | 2,5 |\n\nUn objet est représenté par un triplet contenant son nom (de type `str`), sa valeur (de type `int`) et sa masse (de type `float`).\n\nLes triplets obtenus sont les éléments d’une liste :\n
"},{"metadata":{"trusted":false},"cell_type":"code","source":"objets = [['A', 10, 2], ['B', 11, 4.5], ['C', 23, 5], ['D', 9, 4], ['E', 30, 9], ['F', 6, 1], ['G', 8, 2.5]]","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# 2. La méthode par algorithme glouton"},{"metadata":{},"cell_type":"markdown","source":"!!! note \nOn choisit la stratégie gloutonne suivante : tant qu'il reste un objet transportable, prendre l'objet qui a la plus grande valeur massique $\\mu=\\frac{valeur}{masse}$\n\nPour appliquer cette stratégie, on va devoir trier la liste des objets par ordre décroissant sur les valeurs massiques. Pour ce faire, nous allons utiliser une fonction `liste_triee` qui renvoie la liste des objets disponibles, triée par valeur massique décroissante.\n!!!"},{"metadata":{},"cell_type":"markdown","source":"## 2.1. Préparation de l'algorithme"},{"metadata":{},"cell_type":"markdown","source":"Un objet est représenté par une liste du type ['A', 10, 2].

\nNous allons créer une fonction (`valeurObjets()`) qui rajoute à chaque objet, d'une liste d'objets, sa valeur massique ($\\mu=\\frac{valeur}{masse}$) et renvoie cette liste complétée puis une fonction (`liste_triee()`) qui renvoie cette nouvelle liste, triée par valeur massique décroissante."},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nCompléter la fonction `valeurObjets()` ci-dessous qui prend comme argument une liste d’objets du type [['A', 10, 2], ['B', 11, 4.5], ...] et qui renvoie la valeur de tous ces objets.\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def valeurObjets(liste):\n ''' Entrée : une liste d'objets du type [['A', 10, 2], ['B', 11, 4.5], ...]\n Sortie : un entier corespondant à la valeur totale (en €) des objets de la liste des objets dans \"liste\"\n '''\n valeur = 0\n for objet in ...:\n valeur += ...\n return ...","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vous pouvez faire vos tests ici\n","execution_count":null,"outputs":[]},{"metadata":{"editable":false,"deletable":false,"trusted":false},"cell_type":"code","source":"# Test de la fonction précédente\n# Test final de la fonction valeurObjets()\n# Si votre fonction est correcte alors aucun message d'erreur ne devrait apparaitre après l'exécution de cette cellule\n\nobjets = [['A', 10, 2], ['B', 11, 4.5], ['C', 23, 5], ['D', 9, 4], ['E', 30, 9], ['F', 6, 1], ['G', 8, 2.5]]\n\nassert valeurObjets([['A', 10, 2],['B', 11, 4.5],['C', 23, 5]]) == 44\nassert valeurObjets([['A', 10, 2], ['B', 11, 4.5], ['C', 23, 5], ['D', 9, 4], ['E', 30, 9], ['F', 6, 1], ['G', 8, 2.5]]) == 97","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nCompléter la fonction `liste_triee()` ci-dessous qui prend comme argument une liste d’objets, du type [['A', 10, 2], ['B', 11, 4.5], ...], qui rajoute à chaque objet sa valeur massique et qui renvoie une liste triée par valeur massique décroissante.\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def liste_triee(liste):\n ''' Entrée : une liste d'objets du type [['A', 10, 2], ['B', 11, 4.5], ...]\n Sortie : la liste des objets dans \"liste\", triée par valeur massique décroissante\n '''\n L = [] # initialisation de la liste des objets avec leur valeur massique\n for objet in liste:\n objet.append(... / ...) # calcul de la valeur massique de l'objet en cours d'examen et ajout à sa liste de caractéristiques\n L.append(...) # ajout de l'objet à la nouvelle liste des objets, contenant, en plus, leur valeur massique\n L.sort(key = lambda x : ..., reverse = True) # il faut faire le tri sur la valeur à l'index 3\n return ...","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Tests ici\n","execution_count":null,"outputs":[]},{"metadata":{"editable":false,"deletable":false,"trusted":false},"cell_type":"code","source":"# Cette cellule NE DOIT PAS ETRE modifiée\n# Test final de la fonction rebdu_monnaie\n# Si votre fonction est correcte alors aucun message d'erreur ne devrait apparaitre après l'exécution de cette cellule\n\nobjets = [['A', 10, 2], ['B', 11, 4.5], ['C', 23, 5], ['D', 9, 4], ['E', 30, 9], ['F', 6, 1], ['G', 8, 2.5]]\nassert liste_triee(objets) == [['F', 6, 1, 6.0], ['A', 10, 2, 5.0], ['C', 23, 5, 4.6], ['E', 30, 9, 3.3333333333333335], ['G', 8, 2.5, 3.2], ['B', 11, 4.5, 2.4444444444444446], ['D', 9, 4, 2.25]]","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"## 2.2. Mise en œuvre de l'algorithme"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nCompléter la fonction `sacAdosGlouton()` suivante qui prend comme arguments une liste triée d'objets du type [['A', 10, 2], ['B', 11, 4.5], ...] et un nombre entier correspondant à la capacité du sac à dos puis, après avoir rajouté les valeurs massiques aux objets (appel à la fonction `liste_triee()` définie précédemment), renvoie la liste des noms des objets à prendre conformément à la stratégie gloutonne définie plus haut.\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def sacAdosGlouton(liste, masseMax):\n ''' Entrée : une liste d'objets (liste), du type [['A', 10, 2], ['B', 11, 4.5], ...], et un nombre entier (masseMax)\n Sortie : la liste des noms des objets renvoyée par l'algorithme glouton\n '''\n L = liste_triee(...) # appel de la fonction liste_triee() pour ajouter les valeurs massiques aux objets et trier la liste\n masse_des_objets = 0 # masse totale des objets qui vont être choisis\n listeObjetsAprendre = [] # initialisation de la liste des noms des objets qui vont être choisis\n i = 0\n while masse_des_objets + L[i][2] <= masseMax and i < len(liste):\n listeObjetsAprendre.append(...) # ajout du nom de l'objet choisi à la liste des objets à prendre\n masse_des_objets += ... # ajout de la masse de l'objet à la masse totale des objet retenus\n i += 1\n return ...","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vous pouvez faire des tests ici\n","execution_count":null,"outputs":[]},{"metadata":{"editable":false,"deletable":false,"trusted":false},"cell_type":"code","source":"# Cette cellule NE DOIT PAS ETRE modifiée\n# Test final de la fonction rebdu_monnaie\n# Si votre fonction est correcte alors aucun message d'erreur ne devrait apparaitre après l'exécution de cette cellule\n\nobjets = [['A', 10, 2], ['B', 11, 4.5], ['C', 23, 5], ['D', 9, 4], ['E', 30, 9], ['F', 6, 1], ['G', 8, 2.5]]\nassert sacAdosGlouton(objets, 10) == ['F', 'A', 'C']\nassert [sacAdosGlouton(objets, x) for x in range(20)] == [[], ['F'], ['F'], ['F', 'A'], ['F', 'A'], ['F', 'A'], ['F', 'A'], ['F', 'A'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C', 'E'], ['F', 'A', 'C', 'E'], ['F', 'A', 'C', 'E']]","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"
\n\n### Question 1\nEcrire les instructions permettant de calculer la valeur (en €) de la liste des objets renvoyée par l’algorithme glouton."},{"metadata":{"trusted":false},"cell_type":"code","source":"# Votre code ici\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"
\n\n### Question 2\n \nL'algorithme glouton est-il optimal pour le problème du sac à dos ?"},{"metadata":{},"cell_type":"raw","source":"# Votre réponse :\n"},{"metadata":{},"cell_type":"markdown","source":"# 3. Pour aller plus loin"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nCompléter la fonction ci-dessous puis la tester. Elle doit renvoyer une liste triée (par ordre décroissant des valeurs massiques) de dictionnaires des objets.\n\nVérifier que cette liste est correctement triée et que les valeurs massiques correspondent au tableau suivant :\n\n| Objet | A | B | C | D | E | F | G |\n| :--------------- |:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Valeur (en €) | 10 | 11 | 23 | 9 | 30 | 6 | 8 |\n| Masse (en kg) | 2 | 4,5 | 5 | 4 | 9 | 1 | 2,5 |\n| $\\mu$ (en € / kg)| 5 |2,44 | 4,6 | 2,25| 3,33| 6 | 3,2 |\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def listeDictionnaires(liste):\n '''Entrée: liste d'objets du type [['A', 10, 2], ['B', 11, 4.5], ...]\n Sortie : liste de dictionnaires triée par valeurs massiques décroissantes\n '''\n L = []\n for objet in liste:\n d = dict()\n d['Nom'] = ...\n d['Valeur'] = ...\n d['Masse'] = ...\n d['ValeurMassique'] = ...\n L.append(...)\n L.sort(key = lambda x: x[...], reverse = True) # il faut faire le tri sur la clé \"ValeurMassique\"\n return ...","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vous pouvez faire vos tests ici\n","execution_count":null,"outputs":[]},{"metadata":{"editable":false,"deletable":false,"trusted":false},"cell_type":"code","source":"# Cette cellule NE DOIT PAS ETRE modifiée\n# Test final de la fonction rebdu_monnaie\n# Si votre fonction est correcte alors aucun message d'erreur ne devrait apparaitre après l'exécution de cette cellule\n\nobjets = [['A', 10, 2], ['B', 11, 4.5], ['C', 23, 5], ['D', 9, 4], ['E', 30, 9], ['F', 6, 1], ['G', 8, 2.5]]\nassert listeDictionnaires(objets)==[{'Nom': 'F', 'Valeur': 6, 'Masse': 1, 'ValeurMassique': 6.0}, {'Nom': 'A', 'Valeur': 10, 'Masse': 2, 'ValeurMassique': 5.0}, {'Nom': 'C', 'Valeur': 23, 'Masse': 5, 'ValeurMassique': 4.6}, {'Nom': 'E', 'Valeur': 30, 'Masse': 9, 'ValeurMassique': 3.3333333333333335}, {'Nom': 'G', 'Valeur': 8, 'Masse': 2.5, 'ValeurMassique': 3.2}, {'Nom': 'B', 'Valeur': 11, 'Masse': 4.5, 'ValeurMassique': 2.4444444444444446}, {'Nom': 'D', 'Valeur': 9, 'Masse': 4, 'ValeurMassique': 2.25}]","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nCompléter la fonction `sacAdosGlouton()` ci-dessous puis la tester. Elle doit renvoyer le même résultat que la fonction analogue du $3.2.\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"def sacAdosGlouton(liste, masseMax):\n ''' Entrée : une liste d'objet du type [['A', 10, 2], ['B', 11, 4.5], ...] et un entier masseMax (capacité du sac à dos)\n Sortie : la liste des objets renvoyée par l'algorithme glouton\n '''\n L = listeDictionnaires(...)\n masse_des_objets = 0\n listeObjetsAprendre = []\n i = 0\n while masse_des_objets + L[i][...] <= masseMax and i < len(liste):\n listeObjetsAprendre.append(L[i][...])\n masse_des_objets += L[i][...]\n i += 1\n return ...","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vous pouvez faire vos tests ici\n","execution_count":null,"outputs":[]},{"metadata":{"editable":false,"deletable":false,"trusted":false},"cell_type":"code","source":"# Cette cellule NE DOIT PAS ETRE modifiée\n# Test final de la fonction rebdu_monnaie\n# Si votre fonction est correcte alors aucun message d'erreur ne devrait apparaitre après l'exécution de cette cellule\n\nobjets = [['A', 10, 2], ['B', 11, 4.5], ['C', 23, 5], ['D', 9, 4], ['E', 30, 9], ['F', 6, 1], ['G', 8, 2.5]]\nassert sacAdosGlouton(objets, 10) == ['F', 'A', 'C']\nassert [sacAdosGlouton(objets, x) for x in range(20)] == [[], ['F'], ['F'], ['F', 'A'], ['F', 'A'], ['F', 'A'], ['F', 'A'], ['F', 'A'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C'], ['F', 'A', 'C', 'E'], ['F', 'A', 'C', 'E'], ['F', 'A', 'C', 'E']]","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"# 4. Pour aller encore plus loin"},{"metadata":{},"cell_type":"markdown","source":"!!! question Travail à faire\nIl s'agit de convertir la liste initiale des objets en une liste de dictionnaires contenant, en plus des valeurs initiales (Nom, Valeur et Masse), la valeur massique puis réécrire les fonctions `valeurObjets()`, `liste_tries()` et `sacAdosGlouton()` en conséquence en faisant une sélection des objets non pas par valeur massique la plus élevée possible mais par valeur (en €) la plus élevée possible.\n!!!"},{"metadata":{"trusted":false},"cell_type":"code","source":"# Votre code ici\n","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"# Vous pouvez faire vos tests ici\n","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"name":"python3","display_name":"Python 3","language":"python"},"celltoolbar":"Éditer les Méta-Données"},"nbformat":4,"nbformat_minor":2}