Table des matières

Problème du sac à dos

Problème du sac à dos

Version programmation dynamique

Qu'est-ce ?

Un problème classique d'algorithmique. On dispose d'un sac de capacité $C$ et 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.

On peut voir cela comme un problème de cambrioleur : le cambrioleur dispose d'un sac de taille forcément limitée, et se demande ce qu'il a intérêt à voler. On comprend qu'il prendra des bijoux qui sont précieux et peu encombrant. Prendra-t-il une statuette ? un appareil électronique ? Il cherche à emporter le plus de valeur possible mais est limité par son sac.

Exemple : On dispose d'un sac d'une capacité de $C = 15$ et de la liste d'objets suivants :

Objet	Valeur	Encombrement
A	126	14
B	32	2
C	20	5
D	5	1
E	18	6
F	80	8

Vu en première : L'algorithme glouton

L'algorithme glouton donne une réponse pas forcément optimale au problème posé mais il est simple : On trie le tableau selon un critère puis on remplit le sac en prenant les objets dans l'ordre.

Avec la méthode gloutonne, c'est le tri qui prend le plus de temps : les tris les plus rapides, pour un tableau de taille $n$, sont en $n\log(n)$. La suite de l'algorithme glouton ne nécessite qu'un parcours simple de la liste et est donc en $n$. Globalement, l'algorithme glouton est donc en $n\log(n)$. C'est à dire qu'une liste de taille 100 prend consomme de l'ordre de 200, taille 1000 consomme 3000, 10000 consomme 40000, etc.

Tri par valeur décroissante

Par exemple, si on choisit de trier par valeur décroissante, on obtient :

Objet	Valeur	Encombrement
A	126	14
F	80	8
B	32	2
C	20	5
E	18	6
D	5	1

Puis on complète le sac :

On prend A en premier,
il ne reste alors que 1 kg de place disponible. On ne peut donc pas prendre les items F, B, …
on prend D.

Le sac contiendra A et D totalisant une valeur de 131

Tri par valeur / poids décroissant

On aurait aussi pu trier par rapport valeur / encombrement décroissant

Objet	Valeur	Encombrement	rapport V/E
B	32	2	16
F	80	8	10
A	126	14	9
D	5	1	5
C	20	5	4
E	18	6	3

Dans ce cas on prend B, F, pas A qui ne rentre plus, D, pas C ni E qui ne rentrent plus.

Ce sac contenant B, F, D totalise une valeur de 117.

L'approche gloutonne donne une bonne solution en un temps très court. Mais elle ne donne aucune garantie d'obtenir la meilleure solution. On ne peut pas non plus prévoir quel tri sera le meilleur. Ici, le tri par valeur était meilleur. Avec une autre liste d'objets, le tri par rapport décroissant aurait pu être meilleur.

Programmation dynamique

Principe

L'approche dynamique consiste à étudier des sous-problèmes. Notre problème est constitué d'un sac de capacité $C$ et de 6 objets. On peut noter $msad_{i,c}$ la meilleure réponse dans le problème de sac à dos avec un sac de capacité $c$ et avec les $i$ premiers objets.

Attention, a bien distinguer $c$ et $C$ !

Par exemple $msad_{2,8}$ consiste à résoudre le cas d'un sac de capacité 8 avec seulement les deux objets :

Objet	Valeur	Encombrement
A	126	14
B	32	2

Il devrait être évident que dans ce cas, le meilleur sac contient seulement B. On pourra dire que $msad_{2, 8} = \{ B \}$.

Dans le cas de notre problème, on pourra prendre $0 \leqslant i \leqslant 6$ et $0 \leqslant c \leqslant C = 15$.

Questions

Que vaut $msad_{0,0}$ ?
Plus généralement, que vaut $msad_{i, 0}$ pour tous les $i$ ?
De même, que vaut $msad_{0,c}$ pour tous les $c$ ?
Pour quelle valeur de $i$ et $c$ faut-il trouver $msad_{i,c}$ pour répondre au problème posé au début ?

La méthode dynamique consiste à chercher $msad_{i,c}$ en considérant les valeurs de $msad_{i',c'}$ avec $i' \leq i$ et $c' \leq c$. On cherche donc à remplir un tableau comme celui-ci :

	c = 0	c = 1	c = 2	c = 3	…	c = 14	c = 15
i = 0	$\varnothing$	$\varnothing$	$\varnothing$	$\varnothing$	…	$\varnothing$	$\varnothing$
i = 1	$\varnothing$
…	$\varnothing$
i = 6	$\varnothing$						???

Maintenant, nous devons réfléchir à la façon de progresser dans ce tableau.

Questions

$msad_{2,4}$ est le meilleur sac de capacité 4 avec un choix d'item parmi A, B.
$msad_{3,4}$ est le meilleur sac de capacité 4 avec un choix d'item parmi A, B, C.
Pourquoi puis-je affirmer que $msad_{2,4} = msad_{3,4}$ ?
$msad_{3,7}$ est le meilleur sac de capacité 7 avec un choix d'item parmi A, B, C.
Pourquoi puis-je affirmer que $msad_{3,7}$ est le meilleur entre
- $msad_{2,7}$, meilleur sac de capacité 7 avec un choix d'item parmi A, B,
- $msad_{2,2} \cup \{ C \}$, c'est à dire le meilleur sac de capacité 2 avec un choix d'item parmi A, B, auquel on aurait ajouté C.

D'une façon générale, pour $0 < i$ et $0 < c$, on calcule $msad_{i,c}$ en considérant le meilleur entre :

le sac $msad_{i-1, c}$, c'est à dire le sac de même capacité dans lequel on ne prend pas le i^ème item,
le sac $msad_{i-1, c-p_i} \cup \{\text{i}^\text{ème}\text{ item}\}$, où $p_i$ est le poids du i^ème item, à condition que $p_i \leqslant c$.

Implémentation

Pour les besoins du programme, on stockera les objets dans un tableau :

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

Questions

Écrire une fonction valeur(objets, contenu).
objets est la liste des objets, données plus haut.
contenu est un tableau contenant des indices d'items, par exemple [0, 2] ce qui correspond au contenu $\{A, C\}$.
La fonction renvoie la valeur du sac.
Remarque : on autorise le calcul de la valeur d'un sac indépendamment de la contrainte de capacité.
```
>>> valeur(objets, [0, 2])
146
```
Écrire une fonction encombrement(objets, contenu)
Les arguments sont les mêmes que pour la fonction précédente. Maintenant la fonction renvoie la masse.
```
>>> encombrement(objets, [0, 2])
19
```

On va maintenant réaliser une fonction sacados(objets, capacite) et qui renvoie le meilleur sac à dos avec ces objets et cette capacité. Dans cette fonction, nous utiliserons un tableau à deux dimensions msad contenant le tableau présenté précédemment et que l'on souhaite compléter.

msad[i][c] représentera la liste des indices du meilleur sac à dos en considérant les i premiers items et une capacité c.

Il faudra d'abord initialiser msad connaissant ses dimensions, sa première ligne et sa première colonne, comme vu avant. Il faudra ensuite parcourir les lignes et colonnes pour le compléter de proche en proche en utilisant la règle énoncée plus haut.

Questions

Écrire la fonction sacados
Testez et vérifiez que l'on obtient, pour notre problème, un meilleur sac à dos qu'avec l'algorithme glouton.
Évaluez la complexité temporel de cet algorithme.
On vous fournit les objets sous forme d'un fichier csv liste.csv. Dans ce fichier les encombrements sont exprimés en %, c'est à dire que le sac a une capacité 100.
Écrire la fonction sacados_from_file(filename) qui charge le fichier et renvoie la liste des items à prendre pour produire le meilleur sac à dos.