Ceci est une ancienne révision du document !

Warning: Undefined array key 1 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 172

Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214

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$ en kg 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\,kg$ et de la liste d'objets suivants :

Objet	Valeur	Poids
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	Poids
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 / poids décroissant

Objet	Valeur	Poids	rapport V/P
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 $sad(i, c)$ la meilleur 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 $sad(2, 8)$ consiste à résoudre le cas d'un sac de capacité 8 kg avec seulement les deux objets :

Objet	Valeur	Poids
A	126	14
B	32	2

Il devrait être évident que dans ce cas, le meilleur sac contient seulement B. On pourra dire que $sad(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 $sad(0,0)$ ?
Plus généralement, que vaut $sad(i, 0)$ pour tous les $i$ ?
De même, que vaut $sad(0,c)$ pour tous les $c$ ?
Pour quelle valeur de $i$ et $c$ faut-il trouver $sad(i,c)$ pour répondre au problème posé au début ?

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

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

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

Questions

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

Implémentation

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

objets = [
    ('A', 126, 14),
    ('B', 32, 2),
    ('C', 20, 5),
    ('D', 5, 1),
    ('E', 18, 6),
    ('F', 80, 8)
]

Faites attention que, par exemple, les 3 premiers objets ont les indices 0 à 2.

On créera un tableau à deux dimensions sad contenant le tableau présenté précédemment et que l'on souhaite compléter.

Questions

Comment initialiser sad ?

5. Généralisation. Pour `i > 0`, notons `p_i` le poids de l'objet numéro `i` et `v_i` sa valeur. Justifiez que :

si `c < p_i`, alors `SaD[i][c] = SaD[i-1][c]`
sinon, `SaD[i][c] = max(SaD[i-1][c], SaD[i-1][c - p_i] + v_i)`

6. Réalisez la fonction Python `sacados`prenant un tableau d'objets et la capacité totale en argument et renvoyant la plus haute valeur d'un tel sac.

 Testez et constatez que le résultat est meilleur que celui obtenu avec l'algorithme glouton. Ce choix est optimal.

</markdown>