Ceci est une ancienne révision du document !

---

Warning: Undefined array key "pos" in /home/goupillf/wiki.goupill.fr/lib/plugins/mdpage/src/DokuWiki/Plugin/Mdpage/MarkdownRendererTrait.php on line 100

Warning: Undefined array key "pos" in /home/goupillf/wiki.goupill.fr/lib/plugins/mdpage/src/DokuWiki/Plugin/Mdpage/MarkdownRendererTrait.php on line 100

Warning: Undefined array key "cell_counter" in /home/goupillf/wiki.goupill.fr/inc/parser/xhtml.php on line 1550

Warning: Undefined array key "pos" in /home/goupillf/wiki.goupill.fr/lib/plugins/mdpage/src/DokuWiki/Plugin/Mdpage/MarkdownRendererTrait.php on line 100

Warning: Undefined array key "pos" in /home/goupillf/wiki.goupill.fr/lib/plugins/mdpage/src/DokuWiki/Plugin/Mdpage/MarkdownRendererTrait.php on line 100

13. Problème du sac à dos

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.

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

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.

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

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 suivants sauf le D.

Le sac contiendra A et D totalisant une valeur de 131

On aurait aussi pu trier selon le meilleur rapport valeur / poids

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.

La stratégie précédent était meilleure mais ce n'est pas vrai en général.

Programmation dynamique

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 valeur optimale obtenue dans le problème du sac à dos avec un sac de capacité c et avec les i premiers objets.

Par exemple SaD[2,8] consiste à résoudre le cas d'un sac de capacité 8 kg avec seulement les deux objets :

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

La notation SaD[i][c] avec des crochets est choisis car nous souhaitons stocker tous les résultats intermédiaires dans un tableau.

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 l'objet numéro 3 est l'objet d'indice 2.

Questions :

1. Quelles sont les valeurs de i et c pour lesquelles SaD[i][c] est la réponse au problème initial ?

2. Que peut-on dire de SaD[i][0] pour tous les i ?

3. Que peut-on dire de SaD[0][c] pour tous les c ?

4. On en arrive au point délicat. On va commencez avec deux cas particulier avant de généraliser.

   • Je me demande quelle la plus haute valeur totale d'un sac de capacité 4 kg avec choix parmi A, B, C.

     Pourquoi puis-je affirmer que la réponse est la même que pour le cas 4 kg avec choix parmi A, B ?

   • Je me demande quelle la plus haute valeur totale d'un sac de capacité 7 kg avec choix parmi A, B, C.

     Pourquoi puis-je affirmer que le meilleur choix possible sera :

     • soit le meilleur sac de 7 kg avec choix parmi A, B,
     • soit le meilleur sac de 2 kg avec choix parmi A, B et contenant l'objet C

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