%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Optimisation de problème/Optimisation de problème|Accueil · Optimisation de problème]] > > | [[Code et Développement/Programmation/Optimisation de problème/01_Complexité algorithmique\|← Complexité algorithmique]] | [[Code et Développement/Programmation/Optimisation de problème/03_Satisfaisabilité (SAT)\|Satisfaisabilité (SAT) →]] | > |:---|---:| %% nav-fin %% # Le problème du sac à dos Ce chapitre applique les méthodes d'optimisation au problème du sac à dos. ## Énoncé On dispose de plusieurs objets. Chaque objet a un poids et une valeur. Le sac accepte un poids maximal, appelé capacité. Le problème consiste à choisir les objets à mettre dans le sac pour obtenir la plus grande valeur totale, sans dépasser la capacité. Chaque objet est pris une fois ou pas du tout. La version de décision de ce problème, « existe-t-il un choix d'objets de valeur au moins *V* ? », est NP-complète. Elle fait partie des 21 problèmes NP-complets publiés par Richard Karp en 1972. Les données de l'exemple sont les suivantes. ```python poids = [1, 5, 3, 2, 4] valeurs = [10, 50, 20, 30, 60] capacite = 11 ``` L'objet d'indice *i* a le poids `poids[i]` et la valeur `valeurs[i]`. | Objet | 0 | 1 | 2 | 3 | 4 | |---|---|---|---|---|---| | Poids | 1 | 5 | 3 | 2 | 4 | | Valeur | 10 | 50 | 20 | 30 | 60 | | Valeur / poids | 10 | 10 | 6,67 | 15 | 15 | ## 1. Solution gloutonne La méthode gloutonne classe les objets selon leur rapport valeur / poids, du plus grand au plus petit. Elle ajoute ensuite les objets dans cet ordre, tant qu'ils tiennent dans le sac. ```python def sac_a_dos_glouton(poids, valeurs, capacite): """Renvoie la valeur obtenue par la méthode gloutonne et les objets pris.""" objets = sorted(range(len(poids)), key=lambda i: valeurs[i] / poids[i], reverse=True) pris = [] valeur = 0 for i in objets: if poids[i] <= capacite: capacite -= poids[i] valeur += valeurs[i] pris.append(i) return valeur, pris print(sac_a_dos_glouton(poids, valeurs, capacite)) # (120, [3, 4, 0, 2]) ``` La fonction `sorted` classe les indices des objets. Le paramètre `key` donne le critère de tri, ici le rapport valeur / poids. Le glouton prend les objets 3, 4 et 0, refuse l'objet 1, trop lourd, puis prend l'objet 2. Il obtient une valeur de 120 pour un poids de 10. **À manipuler :** suivez les choix du glouton objet par objet. ```sq-sac poids: 1, 5, 3, 2, 4 valeurs: 10, 50, 20, 30, 60 capacité: 11 mode: glouton ``` Cette solution est rapide, mais elle n'est pas optimale. Les objets 1, 3 et 4 pèsent 5 + 2 + 4 = 11 et valent 50 + 30 + 60 = 140. ## 2. Solution optimale ### La force brute La force brute examine tous les choix possibles d'objets. Avec *n* objets, il y a 2ⁿ choix : chaque objet est pris ou non. Pour 5 objets, on examine 2⁵ = 32 choix. Le nombre de choix double à chaque objet ajouté. La complexité est *O(2ⁿ)*. **À manipuler :** suivez l'examen des 32 choix et repérez le meilleur. ```sq-sac poids: 1, 5, 3, 2, 4 valeurs: 10, 50, 20, 30, 60 capacité: 11 mode: force brute ``` L'algorithme **branch and bound** (séparation et évaluation) améliore la force brute. Il abandonne les choix partiels qui ne peuvent pas dépasser la meilleure solution déjà trouvée. ### La programmation dynamique La programmation dynamique résout le problème sur les *i* premiers objets à partir de la solution sur les *i* − 1 premiers objets. On note T[*i*][*w*] la meilleure valeur obtenue avec les objets 0 à *i* − 1 et une capacité *w*. Pour chaque objet, deux choix sont possibles : - ne pas le prendre : la valeur est T[*i* − 1][*w*] ; - le prendre, s'il tient : la valeur est sa valeur plus T[*i* − 1][*w* − son poids]. T[*i*][*w*] est le plus grand de ces deux nombres. Une fois le tableau rempli, on remonte de la dernière case pour retrouver les objets pris. Si T[*i*][*w*] diffère de T[*i* − 1][*w*], l'objet *i* − 1 est pris. ```python def sac_a_dos_dynamique(poids, valeurs, capacite): """Renvoie la valeur optimale et les objets pris.""" n = len(poids) T = [[0] * (capacite + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(capacite + 1): T[i][w] = T[i - 1][w] if poids[i - 1] <= w: T[i][w] = max(T[i][w], valeurs[i - 1] + T[i - 1][w - poids[i - 1]]) pris = [] w = capacite for i in range(n, 0, -1): if T[i][w] != T[i - 1][w]: pris.append(i - 1) w -= poids[i - 1] return T[n][capacite], sorted(pris) print(sac_a_dos_dynamique(poids, valeurs, capacite)) # (140, [1, 3, 4]) ``` Le tableau compte (*n* + 1) × (capacité + 1) cases. La complexité est *O(n × capacité)*. Cette complexité dépend de la valeur de la capacité, pas seulement du nombre d'objets. Elle n'est pas polynomiale en la taille des données. Le problème reste NP-complet. **À manipuler :** remplissez le tableau case par case ou ligne par ligne, puis suivez la remontée. ```sq-sac poids: 1, 5, 3, 2, 4 valeurs: 10, 50, 20, 30, 60 capacité: 11 mode: dynamique ``` ## Bilan | Méthode | Résultat sur l'exemple | Complexité | |---|---|---| | Glouton | 120, non optimal | *O(n log n)*, coût du tri | | Force brute | 140, optimal | *O(2ⁿ)* | | Programmation dynamique | 140, optimal | *O(n × capacité)* | %% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %% > [!nav] > ↩ [[Code et Développement/Programmation/Optimisation de problème/Optimisation de problème|Accueil · Optimisation de problème]] > > | [[Code et Développement/Programmation/Optimisation de problème/01_Complexité algorithmique\|← Complexité algorithmique]] | [[Code et Développement/Programmation/Optimisation de problème/03_Satisfaisabilité (SAT)\|Satisfaisabilité (SAT) →]] | > |:---|---:| %% nav-fin %%