Problème du sac à dos

Introduction

Objectif

L'objectif de ces travaux pratiques est de comprendre et mettre en oeuvre un algorithme glouton.

Préparation

Afin de garder organisées les productions réalisées en travaux pratiques, veuillez mettre à jour l'arborescence du dossier NSI en fonction l'ordinateur utilisé :

💻 Ordinateur portable

1. Lancer
2. Se rendre dans le dossier Documents
3. Créer le dossier NSI s'il n'existe pas
4. Dans le dossier NSI, créer le dossier chapitre_16
5. Dans le dossier chapitre_16, créer le dossier tp2_sac_a_dos

🖥 Ordinateur fixe des salles informatiques

1. Depuis le bureau, cliquer sur l'icône intitulée Zone personnelle
2. Créer le dossier NSI s'il n'existe pas
3. Dans le dossier NSI, créer le dossier chapitre_16
4. Dans le dossier chapitre_16, créer le dossier tp2_sac_a_dos

Téléchargement des fichiers

Pour effectuer ce TP, il est nécessaire de télécharger certains fichiers :

1. Télécharger le fichier ZIP contenant les fichiers du TP : 📦 télécharger
2. Ouvrir le fichier ZIP
3. Copier/coller tous les fichiers dans le dossier NSI\chapitre_16\tp2_sac_a_dos

Problème du sac à dos

Présentation

On dispose d’un sac pouvant supporter une masse maximale donnée et de divers objets ayant chacun une valeur et une masse.

Le problème est 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.

Ce 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.

Nous pouvons 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/poids le plus grand ? Cela reste à définir.

On va considérer deux sacs à dos de capacités maximales respectives de 20 et 40 kg et pour chacun une table d’objets possibles qui sont fournis avec leur masse et leur valeur dans les fichiers au format CSV :

Sac à dos n°1, masse maximale autorisée : 20 kg

Objets	Valeur	Masse
1	2	10
2	4	14
3	4	7
4	5	3

Sac à dos n°2, masse maximale autorisée : 40 kg

Objets	Valeur	Masse
1	2	10
2	4	11
3	8	7
4	5	5
5	8	6
6	10	15
7	11	8

Représentation des données

La fonction csv_vers_table(chemin) fournie dans glouton.py permet d’extraire dans un tableau de dictionnaires les données stockées dans un fichier CSV comme sac1.csv ou sac2.csv.

Exercice 1

Modifier le fichier exercice1.py de façon en :

• écrivant une expression permettant d'accéder à la valeur de l’objet 2 et en la convertissant en flottant
• écrivant une expression permettant d'accéder à la masse de l’objet 2 et en la convertissant en flottant

Force brute

Une méthode simple de résolution du problème du sac à dos consiste à énumérer l’ensemble de toutes les configurations possibles (compatibles avec la contrainte de masse maximale) et à déterminer la valeur maximale du sac sur cet ensemble.

Malheureusement, l’explosion combinatoire limite cette solution par force brute à un nombre n d’objets réduit car il existe 2ⁿ parties distinctes d’un ensemble à $n$ éléments. Le nombre de parties croît donc de façon exponentielle par rapport au nombre $n$ d’objets.

Il est donc possible de représenter la liste des parties d’un ensemble à n éléments par une représentation binaire sur n bits où 0 et 1 signifie respectivement que l'objet sélectionné et non sélectionné

Par exemple la liste des parties d’un ensemble à 3 éléments est représentée par un tableau de 2³ tableaux de 3 bits :

>>> liste_parties(3)
[[0, 0, 0], [0, 0, 1], [0, 1, 0],[0, 1, 1],
 [1, 0, 0], [1, 0, 1],[1, 1, 0], [1, 1, 1]]

Exercice 2

1. Compléter la fonction incrementation_binaire(tableau_bits) fournie dans glouton.py qui prend en paramètre un tableau de bits représentant le codage binaire d’un entier et renvoie le tableau de bits de son successeur

>>> incrementation_binaire([0, 0])
[0, 1]
>>> incrementation_binaire([0, 1])
[1, 0]
>>> incrementation_binaire([0, 1, 1])
[1, 0, 0]

2. Compléter la fonction liste_parties(n) pour qu’eller envoie la liste des parties d’un ensemble à n éléments :

>>> liste_parties(3)
[[0, 0, 0], [0, 0, 1], [0, 1, 0],[0, 1, 1],
 [1, 0, 0], [1, 0, 1],[1, 1, 0], [1, 1, 1]]

3. Compléter la fonction somme_tab(t) pour qu’elle renvoie la somme des éléments du tableau de nombres t passé en paramètre.

4. Compléter la fonction sac_force_brute(table, masse_max) pour respecter la spécification et le jeu de tests unitaires fournis.

>>> sac1 = csv_vers_table(’sac1.csv’)
>>> sac_force_brute(sac1, 20)
(11.0, [{’objet’: ’1’, ’valeur’: ’2’, ’masse’: ’10’},
  {’objet’: ’3’, ’valeur’: ’4’, ’masse’: ’7’},
  {’objet’: ’4’, ’valeur’: ’5’, ’masse’: ’3’}])

Stratégie gloutonne

Exercice 3

Dans glouton.py, compléter la fonction sac_glouton(table, masse_max) de même spécification que sac_force_brute(table, masse_max).

La sélection des objets doit se faire par choix glouton : on parcourt le tableau de dictionnaires table de son premier élément d’index 0 à son dernier et on sélectionne le premier objet disponible si la contrainte de masse totale du sac peut être respectée.

Exercice 4

Exécutez cette fois la stratégie gloutonne en triant au préalable le tableau d'objets en utilisant les fonctions :

• clef_tri_masse_croissant
• clef_tri_valeur_decroissant
• clef_tri_ratio_decroissant

# Exemple
sorted(objets, key = clef_tri_masse_croissant)

Testez l'algorithme glouton pour les trois tris possibles et les objets des deux sacs. Comparez avec le résultat obtenu en force brute.