Ministère de l’Enseignement Supérieur et de la Recherche Scientifique

Mini projet

Filière : Ingénierie Logicielle et Systèmes d’Information(ILSI)

Module : entrepreneuriat

Programmation dynamique, Le
problème de SAC-à-DOS

Réalisé par :
M. NABGAOUI Khalid Encadré par :
M. AHTI Imad Pr. OUCHAOU Brahim

Promotion : 2023/2024
Table des matières

0.1 Introduction générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

0.1.1 Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.1.2 Objectifs du rapport . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.1.3 Méthodologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.2 Vision globale sur la programmation dynamique . . . . . . . . . . . . . 2
0.2.1 Définition de la programmation dynamique . . . . . . . . . . . . 2
0.2.2 Historique et évolution . . . . . . . . . . . . . . . . . . . . . . . . 2
0.2.3 Applications courantes . . . . . . . . . . . . . . . . . . . . . . . . 3
0.2.4 Avantages et inconvénients de la programmation dynamique . . . 4
0.3 Principes fondamentaux de la programmation dynamique . . . . . . . . . 5
0.3.1 Sous-structure optimale . . . . . . . . . . . . . . . . . . . . . . . 5
0.3.2 Recouvrement des sous-problèmes . . . . . . . . . . . . . . . . . . 5
0.3.3 Relation de récurrence . . . . . . . . . . . . . . . . . . . . . . . . 5
0.4 LE PROBLÈME DU SAC À DOS ILLIMITÉ . . . . . . . . . . . . . . . 7
0.4.1 Définition et formulation du problème . . . . . . . . . . . . . . . 7
0.4.2 Variantes du Problème de Sac à Dos . . . . . . . . . . . . . . . . 8
0.4.3 Applications Pratiques : . . . . . . . . . . . . . . . . . . . . . . . 8
0.5 Implémentation d’un algorithme de
programmation dynamique pour le sac à dos . . . . . . . . . . . . . . . . 10
0.5.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
0.5.2 méthodes de résolution de problème de sac à dos . . . . . . . . . 11
0.5.3 Algorithme de Résolution du Problème de Sac à Dos . . . . . . . 14
0.5.4 Complexité Temporelle . . . . . . . . . . . . . . . . . . . . . . . . 14
0.6 Modèles de chemins : équation de récurrence et algorithme . . . . . . . . 15
0.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

i
0.1. INTRODUCTION GÉNÉRALE

0.1 Introduction générale

0.1.1 Contexte
La programmation dynamique, une technique algorithmique puissante, trouve son ap-
plication dans la résolution efficace de problèmes complexes en décomposant ces derniers
en sous-problèmes plus simples. Cette approche permet d’obtenir des solutions optimales
grâce à la résolution itérative des sous-problèmes, évitant ainsi la duplication des calculs.
Dans ce rapport, nous explorons les fondements de la programmation dynamique et son
application à un problème spécifique : le problème du sac à dos

0.1.2 Objectifs du rapport

L’objectif principal de ce rapport est de familiariser le lecteur avec les concepts fon-
damentaux de la programmation dynamique et de démontrer leur application à travers
le problème du sac à dos. Les points spécifiques que nous aborderons sont les suivants :

• Comprendre les concepts de base de la programmation dynamique : Nous explore-

rons les principes sous-jacents de cette approche algorithmique, mettant en évidence
son utilité dans la résolution de problèmes complexes.
• Appliquer ces concepts à un problème concret - le problème du sac à dos : Nous
examinerons en détail le problème du sac à dos, un problème d’optimisation bien
connu, et illustrerons comment la programmation dynamique peut être utilisée pour
obtenir des solutions optimales.
• En détaillant ces aspects, ce rapport vise à offrir une compréhension approfondie
de la programmation dynamique tout en présentant un exemple concret de son
application, jetant ainsi les bases pour la suite de notre exploration.

0.1.3 Méthodologie
Pour atteindre ces objectifs, notre approche repose sur une méthodologie rigoureuse.
Nous avons mené une recherche approfondie, recueilli des données pertinentes, et utilisé
des outils d’analyse avancés pour garantir la fiabilité et la pertinence de nos conclusions.

1
0.2. VISION GLOBALE SUR LA PROGRAMMATION DYNAMIQUE

0.2 Vision globale sur la programmation dynamique

0.2.1 Définition de la programmation dynamique
La programmation dynamique est une méthode de construction d’algorithme très
utilisée en optimisation combinatoire (→ recherche de solution optimale dans un ensemble
fini de solutions mais très grand). Il s’agit d’une méthode d’énumération implicite (idem
PSE) : on retient ou rejette des sous-ensembles de solutions mais on ne construit pas
toutes les solutions. On rejette certaines solutions sans les avoir construites explicitement
si elles appartiennent à un sous-ensemble qui n’est pas intéressant.

0.2.2 Historique et évolution

• 1953 Développement du Paradigme : Richard Bellman développe le paradigme

de la programmation dynamique chez RAND Corporation. « Programmation » =
planification

• Origine du Terme ”Programmation Dynamique : Le terme ”programmation

dynamique” est introduit par Bellman, mais il choisit ce nom pour des raisons de
marketing plutôt que pour décrire le processus de programmation au sens tradi-
tionnel. Il cherchait à éviter des connotations négatives associées à d’autres termes
de l’époque.

• Application aux Problèmes d’Optimisation : La programmation dynamique

est reconnue comme une technique de conception d’algorithme très générale et per-
formante, particulièrement adaptée à la résolution de problèmes d’optimisation.

• Développement de la Méthodologie : Au fil des années, la programmation

dynamique développe une méthodologie structurée basée sur la décomposition de
problèmes complexes en sous-problèmes plus simples.

2
0.2. VISION GLOBALE SUR LA PROGRAMMATION DYNAMIQUE

• Évolution Théorique et Algorithmique : Des chercheurs approfondissent la

théorie derrière la programmation dynamique, améliorant les algorithmes existants
et en proposant de nouvelles variantes.

• Évolutions Contemporaines : La programmation dynamique continue d’évoluer

avec les avancées technologiques et les besoins croissants en termes de résolution de
problèmes complexes. Elle reste un domaine de recherche actif et un outil essentiel
pour les informaticiens et les chercheurs.

0.2.3 Applications courantes

La programmation dynamique, en tant que méthodologie puissante d’optimisation al-
gorithmique, trouve des applications étendues qui transcendent les frontières de nombreux
domaines. Son impact se manifeste de manière significative dans des contextes pratiques
variés, où la résolution de problèmes complexes exige une approche méthodique et effi-
cace. Parmi ces domaines, on trouve

Planification de Production : Dans le domaine de la gestion de la production, la

programmation dynamique peut aider à optimiser la planification des ressources, mini-
miser les coûts de production et maximiser l’efficacité opérationnelle.

Réseaux de Communication : Dans la conception de protocoles de communication,

la programmation dynamique peut être utilisée pour optimiser l’utilisation des canaux
de communication, améliorant ainsi l’efficacité du transfert de données.

Algorithmes de Chemin le Plus Court : Les algorithmes de chemin le plus court, tels
que l’algorithme de Bellman-Ford, utilisent la programmation dynamique pour trouver
les chemins les plus courts dans un graphe pondéré.

Algorithmes de Compression de Données : Certains algorithmes de compression

de données utilisent la programmation dynamique pour identifier et éliminer les redon-
dances, réduisant ainsi la taille des fichiers sans perte significative d’information.

3
0.2. VISION GLOBALE SUR LA PROGRAMMATION DYNAMIQUE

0.2.4 Avantages et inconvénients de la programmation dyna-

mique
0.2.4.1 Avantages
• Optimisation Efficace : La programmation dynamique excelle dans la résolu-
tion de problèmes d’optimisation en trouvant la meilleure solution parmi un grand
nombre de possibilités, grâce à la décomposition en sous-problèmes.

• Économie de Calculs :En stockant et réutilisant les résultats intermédiaires, la

programmation dynamique évite de recalculer les mêmes sous-problèmes, ce qui
conduit à une économie significative en termes de ressources computationnelles.

• Adaptabilité à Divers Domaines :Sa flexibilité et sa polyvalence permettent à

la programmation dynamique de s’appliquer avec succès dans des domaines variés
tels que la finance, la biologie, l’informatique, et bien d’autres.

• Gestion de Problèmes Complexes :Elle se révèle particulièrement utile pour

résoudre des problèmes complexes, où la recherche exhaustive de solutions devien-
drait impraticable en raison de la taille de l’espace des solutions.

0.2.4.2 Inconvénients
• Complexité Conceptuelle : Comprendre et concevoir des solutions en utilisant
la programmation dynamique peut être complexe, en particulier pour des problèmes
novateurs ou pour des personnes peu familières avec cette approche.

• Espace Mémoire Requis :Certains algorithmes de programmation dynamique

peuvent nécessiter un espace mémoire considérable, en particulier lorsqu’ils stockent
des résultats intermédiaires, ce qui peut être un inconvénient pour des problèmes
de grande envergure.

• Choix de la Sous-Structure :La décomposition du problème en sous-problèmes

doit être faite judicieusement, et un mauvais choix peut entraîner des résultats non
optimaux.

4
0.3. PRINCIPES FONDAMENTAUX DE LA PROGRAMMATION DYNAMIQUE

0.3 Principes fondamentaux de la programmation dy-

namique
0.3.1 Sous-structure optimale
Le principe de sous-structure optimale est l’un des fondements essentiels de la pro-
grammation dynamique. Il repose sur l’idée qu’une solution optimale à un problème global
peut être construite à partir de solutions optimales de ses sous-problèmes. En d’autres
termes, si l’on divise un problème en sous-problèmes plus petits et que l’on peut trouver
la meilleure solution pour chacun de ces sous-problèmes, alors la solution optimale du
problème global peut être déduite de manière efficace.

En bref, Le principe de sous-structure optimale permet de décomposer un problème

complexe en parties plus simples et de résoudre chaque partie de manière indépendante.
Les résultats intermédiaires sont souvent stockés dans une table (mémoire), ce qui évite
de recalculer les mêmes sous-problèmes plusieurs fois.

0.3.2 Recouvrement des sous-problèmes

Le recouvrement des sous-problèmes s’appuie sur l’idée que lors de la résolution d’un
problème complexe, certains sous-problèmes peuvent se recouvrir, c’est-à-dire qu’ils par-
tagent des solutions communes. Plutôt que de recalculer ces solutions à chaque occurrence,
la programmation dynamique optimise en stockant les résultats intermédiaires dans une
table de mémoire.

Lorsqu’il y a du recouvrement des sous-problèmes, le stockage des résultats dans la

mémoire permet d’éviter la redondance des calculs. Au lieu de résoudre à nouveau un
sous-problème déjà traité, le programme dynamique récupère simplement la solution sto-
ckée en mémoire. Cela conduit à des gains d’efficacité significatifs, surtout lorsque les
sous-problèmes sont fréquemment réutilisés dans la résolution globale du problème.

Il contribue ainsi à réduire la complexité temporelle des algorithmes en éliminant

les calculs redondants, faisant de la programmation dynamique une méthode particuliè-
rement adaptée pour traiter des problèmes où des parties du problème global se che-
vauchent. Cette propriété, combinée au principe de sous-structure optimale, renforce
l’efficacité globale de la programmation dynamique dans la résolution de problèmes com-
plexes.

0.3.3 Relation de récurrence

La relation de récurrence constitue un pilier central dans la conception et l’analyse
des algorithmes de programmation dynamique. Elle se manifeste sous la forme d’une
équation qui exprime la relation entre la solution d’un problème global et celles de ses
sous-problèmes. En d’autres termes, la relation de récurrence définit comment les so-
lutions optimales des sous-problèmes contribuent à construire la solution optimale du

5
0.3. PRINCIPES FONDAMENTAUX DE LA PROGRAMMATION DYNAMIQUE

problème global.
Cette relation, souvent dérivée de la sous-structure optimale, fournit le modèle mathé-
matique qui guide la décomposition du problème en sous-problèmes et la reconstruction
de la solution optimale à partir de ces sous-solutions. La clarté et la précision de la re-
lation de récurrence sont cruciales pour garantir la validité et l’efficacité de l’algorithme
de programmation dynamique.

Dans la pratique, la relation de récurrence est souvent formulée de manière récursive,

exprimant la solution d’un problème en fonction de solutions de problèmes plus petits.
Elle peut également inclure des termes qui correspondent aux coûts, aux valeurs, ou aux
poids associés aux sous-problèmes.

6
0.4. LE PROBLÈME DU SAC À DOS ILLIMITÉ

0.4 LE PROBLÈME DU SAC À DOS ILLIMITÉ

0.4.1 Définition et formulation du problème
Le problème du sac à dos illimité (UKP) est un problème d’optimisation NP-difficile
largement étudié avec une large gamme d’applications dans l’industrie et la gestion fi-
nancière. De manière informelle, un ensemble N de types d’éléments est donné, chaque
type d’élément i a un poids w et un profit p. Le but est de remplir un sac à dos de
capacité limitée C avec une combinaison linéaire des types d’articles dans N, en maxi-
misant la somme des profits des articles sélectionnés et en respectant la contrainte de
capacité. Considérant � N comme variable de décision qui indique le nombre de copies du
type d’élément i dans la solution, alors le problème du sac à dos illimité peut être énoncé
comme un programme linéaire entier :

∑
max xi pj
j∈N
∑
s.t. xj w j ≤ C
j∈N

xj ∈ N ∀j ∈ N

UKP fait partie d’une famille de problèmes appelés problèmes de sac à dos. On l’ap-
pelle illimité car chaque type d’élément dans N peut être utilisé autant de fois que néces-
saire. D’autres variantes de problèmes de sac à dos incluent des problèmes dans lesquels
seul un nombre limité d’éléments de chaque type peut être utilisé (problème de sac à dos
limité) et des problèmes dans lesquels chaque type d’élément ne peut être utilisé qu’une
seule fois (problème de sac à dos 0-1).

Même s’il existe un nombre illimité d’éléments disponibles de chaque type, la quantité
d’éléments dans une solution est naturellement limitée par la capacité du sac à dos. Ainsi,
un solveur pour le problème du sac à dos borné résout également l’UKP si nous fixons
les limites b ; sur chaque article i (le nombre maximum de chaque type d’article autorisé
dans le sac à dos) comme la capacité C divisée par son poids w. La même chose peut
être dite pour le problème du sac à dos 0-1 : une instance UKP peut être transformée en
une instance du problème du sac à dos 0-1 si nous créons b copies de chaque élément i.
L’utilisation des transformations susmentionnées pour résoudre les instances UKP montre
de mauvaises performances en pratique. Afin d’utiliser un solutionneur de problèmes de
sac à dos 0-1, un grand nombre d’éléments doivent être créés, en particulier lorsque la
capacité du sac à dos est grande, ce qui augmente le temps de traitement et la quantité de
mémoire requise. Il existe également certaines propriétés de l’UKP (à savoir la dominance
et la périodicité) qui ne sont pas présentes dans d’autres variantes. De telles propriétés
peuvent être exploitées par un algorithme spécifique à l’UKP.
Il existe deux méthodes classiques et exactes pour résoudre l’UKP : Branch Bound
et Dynamic Programming. Dans ce chapitre, les deux techniques sont expliquées. Ces
techniques exploitent la propriété de domaine pour résoudre UKP.

7
0.4. LE PROBLÈME DU SAC À DOS ILLIMITÉ

0.4.2 Variantes du Problème de Sac à Dos

Le problème du sac à dos peut prendre différentes formes en fonction des contraintes
spécifiques imposées. Quelques variantes courantes incluent : :

1. Sac à Dos à Capacité Illimitée (Unbounded Knapsack Problem - UKP) :

Les objets peuvent être sélectionnés un nombre illimité de fois.

2. Sac à Dos Fractionnaire :Les objets peuvent être fractionnés, permettant de

prendre des parties d’objets.

3. Problème du Sac à Dos Multi-dimensionnel :Les objets ont plusieurs pro-

priétés, et le sac à dos a plusieurs capacités.

4. Problème du Sac à Dos Bidimensionnel :Les objets ont deux attributs (par
exemple, poids et volume) et le sac à dos a deux capacités.

0.4.3 Applications Pratiques :

Le problème du sac à dos trouve des applications pratiques dans divers domaines,
notamment :

Gestion des Stocks : Maximiser la valeur des produits stockés tout en respectant les
contraintes d’espace d’entreposage.

Finance : Sélectionner des investissements pour maximiser le rendement tout en respec-

tant les contraintes budgétaires.

Transport : Maximiser la valeur des marchandises transportées en respectant les limites

de poids et d’espace.

Planification de Projet : Optimiser la sélection des tâches à accomplir pour maximiser

le rendement dans un projet limité par le temps.

Ce problème, par sa simplicité apparente, cache des complexités algorithmiques inté-

ressantes. Dans la suite de ce rapport, nous explorerons les solutions à ce problème en
utilisant la programmation dynamique, en mettant particulièrement l’accent sur le cas
du Sac à Dos Non Borne (Unbounded Knapsack Problem - UKP).

8
0.5. IMPLÉMENTATION D’UN ALGORITHME DE
PROGRAMMATION DYNAMIQUE POUR LE SAC À DOS
0.5 Implémentation d’un algorithme de
programmation dynamique pour le sac à dos
0.5.1 Example
Toute formulation commence par un énoncé des données. Dans notre cas, nous avons
un sac à dos de poids maximal W et n objets. Pour chaque objet i, nous avons un poids
wi et une valeur pi .
Pour quatre objets (n = 4) et un sac à dos d’un poids maximal de 30 kg(W = 30),
nous avons par exemple les données suivantes :

Objets 1 2 3 4
pi 7 4 3 3 �
Wi 13 12 8 10

Ensuite, il nous faut définir les variables qui représentent en quelque sorte les actions ou
les décisions qui amèneront à trouver une solution. On définit la variable xi associée à un
objet i de la façon suivante : xi = 1 si l’objet i est mis dans le sac, et xi = 0 si l’objet i
n’est pas mis dans le sac.
Dans notre exemple, une solution réalisable est de mettre tous les objets dans le sac à
dos sauf le premier, nous avons donc : x1 = 0, x2 = 1, x3 = 1, etx4 = 1.
Puis il faut définir les contraintes du problème. Ici, il n’y en a qu’une : la somme des
poids de tous les objets dans le sac doit être inférieure ou égale au poids maximal du sac
à dos.
Cela s’écrit : x1 .w1 + x2 .w2 + x3 .w3 + x4 .w4 ≤ W
ou plus généralement pour n objets :
∑
n
xi .wi ≤ W
i=1

Pour vérifier que la contrainte est respectée dans notre exemple, il suffit de calculer cette
somme : 0×13 + 1×12 + 1×8 + 1×10 = 30, ce qui est bien inférieur ou égal à 30, donc
la contrainte est respectée. Nous parlons alors de solution réalisable. Mais ce n’est pas
nécessairement la meilleure solution.
Enfin, il faut exprimer la fonction qui traduit notre objectif : maximiser la valeur totale
des objets dans le sac.
Pour n objets, cela s’écrit :
∑
n
max xi .pi
i=1

Dans notre exemple, la valeur totale contenue dans le sac est égale à 10. Cette solution
n’est pas la meilleure, car il existe une autre solution de valeur plus grande que 10 : il faut
prendre seulement les objets 1et2 qui donneront une valeur totale de 11. Il n’existe pas de
meilleure solution que cette dernière, nous dirons alors que cette solution est optimale.

9
0.5. IMPLÉMENTATION D’UN ALGORITHME DE
PROGRAMMATION DYNAMIQUE POUR LE SAC À DOS
0.5.2 méthodes de résolution de problème de sac à dos
Il existe deux grandes catégories de méthodes de résolution de problèmes d’optimi-
sation combinatoire : les méthodes exactes et les méthodes approchées. Les méthodes
exactes permettent d’obtenir la solution optimale à chaque fois, mais le temps de calcul
peut être long si le problème est compliqué à résoudre. Les méthodes approchées, encore
appelées heuristiques, permettent d’obtenir rapidement une solution approchée, donc pas
nécessairement optimale. Nous allons détailler un exemple d’algorithme de résolution de
chaque catégorie.

0.5.2.1 Méthode approchée

Une méthode approchée a pour but de trouver une solution avec un bon compromis
entre la qualité de la solution et le temps de calcul. Pour le problème du sac à dos, voici
un exemple d’algorithme de ce type :

• DEBUT
• calculer la valeur (pi / wi) pour chaque objet i,
• trier tous les objets par ordre décroissant de cette valeur,
• sélectionner les objets un à un dans l’ordre du tri et ajouter l’objet sélectionné dans
le sac si le poids maximal reste respecté.
• FIN

Déroulons cet algorithme sur notre exemple :

• Première étape :

Objets 1 2 3 4
�
pi /Wi 0.54 0.33 0.37 0.30

• Deuxième étape : l’ordre des objets est donc le suivant : 1, 3, 2, et 4.

• Troisième étape :
• Objet 1 : on le met dans le sac (qui est vide au départ).
• Objet 2 : on le met dans le sac car l’addition du poids de l’objet 1 et de
l’objet 3 est inférieure à 30.
• Objet 3 : on ne le met pas dans le sac car le poids total (33) dépasse le poids
maximal du sac.
• Objet 4 : on ne le met pas dans le sac pour la même raison que pour l’objet
2.
La solution trouvée est donc de mettre les objets 1 et 3 dans le sac, ce qui donne une
valeur de 10. Cette solution n’est pas optimale, puisqu’une solution avec une va-
leur totale de 11 existe. Néanmoins, cet algorithme reste rapide même si le nombre
d’objets augmente considérablement.
Ce type d’algorithme est aussi appelé algorithme glouton, car il ne remet jamais en

10
0.5. IMPLÉMENTATION D’UN ALGORITHME DE
PROGRAMMATION DYNAMIQUE POUR LE SAC À DOS
cause une décision prise auparavant. Ici, lorsque l’objet 2 ne peut pas entrer dans
le sac, l’algorithme n’essaie pas d’enlever l’objet 3 du sac pour y mettre l’objet 2 à
sa place.

Hormis les algorithmes gloutons, il existe un grand nombre de méthodes appro-

chées : les méthodes de recherche « tabou », les algorithmes génétiques, les
algorithmes de descente locale, ou même des algorithmes à base de fourmis
artificielles.

0.5.2.2 Méthode exacte

Pour trouver la solution optimale, et être certain qu’il n’y a pas mieux, il faut utiliser
une méthode exacte, qui demande un temps de calcul beaucoup plus long (si le problème
est difficile à résoudre). Il n’existe pas une méthode exacte universellement plus rapide que
toutes les autres. Chaque problème possède des méthodes mieux adaptées que d’autres.
Nous allons présenter un exemple d’algorithme de ce type, nommé procédure par sé-
paration et évaluation (PSE), ou en anglais branch and bound. Nous n’exposerons ici
qu’une version simplifiée d’une PSE.

Une PSE est un algorithme qui permet d’énumérer intelligemment toutes les solutions
possibles. En pratique, seules les solutions potentiellement de bonne qualité seront énu-
mérées, les solutions ne pouvant pas conduire à améliorer la solution courante ne sont pas
explorées. Pour représenter une PSE, nous utilisons un « arbre de recherche » constitué :

• de nœuds ou sommets, où un nœud représente une étape de construction de la

solution
• d’arcs pour indiquer certains choix faits pour construire la solution.

Dans notre exemple, les nœuds représentent une étape où un certain nombre d’objets
auront été mis dans le sac, d’autres laissés en dehors du sac, et d’autres objets pour
lesquels aucune décision n’a encore été prise. Chaque arc indique l’action de mettre un
objet dans le sac ou au contraire de ne pas le mettre dans le sac. La figure suivante
représente une partie de l’arbre de recherche.

11
0.5. IMPLÉMENTATION D’UN ALGORITHME DE
PROGRAMMATION DYNAMIQUE POUR LE SAC À DOS
À partir d’une étape N , l’algorithme construit deux nouvelles étapes : dans celle de
gauche, on conserve toutes les décisions prises à l’étape N et on ajoute la décision de mettre
un nouvel objet (ici l’objet i) dans le sac ; dans celle de droite, on conserve également
toutes les décisions prises à l’étape N et on ajoute la décision de ne pas mettre l’objet i.
L’arbre de recherche commence par un seul nœud, où aucune décision n’a été prise pour

les objets. Une fois tous les objets sélectionnés, les nœuds finaux, aussi appelés nœuds
feuilles, représentent chacun une solution finale. La figure suivante reprend l’exemple
précédent et représente l’arbre de recherche induit.

Les nœuds en rouge représentent une solution impossible. Par exemple, pour le nœud
tout à gauche en rouge, il est impossible de prendre les trois premiers objets à cause
du poids maximal à ne pas dépasser. Il n’est donc pas nécessaire de développer l’étape
suivante avec le dernier objet. Les nœuds en bleu sont des nœuds feuilles correspondant à
une solution réalisable. À la fin de l’algorithme, il suffit de calculer la valeur du sac pour
chaque nœud feuille et de prendre la solution avec la plus grande valeur. La figure n’expose
pas tous les nœuds feuilles, étant donné qu’il y en a beaucoup seulement avec 4 objets.
Et plus le nombre d’objets augmente, plus le nombre de feuilles augmente rapidement.
On parle de croissance exponentielle.

Il existe de nombreuses techniques d’amélioration de parcours de ce type d’arbre. Ces

techniques ont pour but de diminuer la taille de l’arbre et d’augmenter la rapidité.
Un élément essentiel dans une PSE est le calcul de bornes, inférieures et supérieures, de
la fonction objectif.

• une borne inférieure est une valeur minimum de la fonction objectif. Autrement dit,
c’est une valeur qui est nécessairement inférieure à la valeur de la meilleure solution
possible. Dans notre cas, une configuration du sac réalisable quelconque fournit une
borne inférieure.

12
0.5. IMPLÉMENTATION D’UN ALGORITHME DE
PROGRAMMATION DYNAMIQUE POUR LE SAC À DOS
• une borne supérieure est une valeur maximale de la fonction objectif. Autrement
dit, nous savons que la meilleure solution a nécessairement une valeur plus petite.
Dans notre cas, nous savons que la valeur de la meilleure solution est nécessairement
inférieure à la somme des valeurs de tous les objets (comme si on pouvait tous les
mettre dans le sac).

0.5.3 Algorithme de Résolution du Problème de Sac à Dos

L’algorithme de résolution du problème de sac à dos par programmation dynamique
peut être décomposé en plusieurs étapes. Voici une approche générale :

1. Initialisation : Créer une table de programmation dynamique de taille

(n + 1)×(W + 1) où n est le nombre d’objets et W est la capacité du sac à dos.
2. Remplissage de la Table : Remplir la table en utilisant la relation de récurrence
propre au problème du sac à dos. Pour chaque cellule dp [i][w], où i est le nombre
d’objets considérés et w est la capacité restante du sac à dos, calculer le maximum
entre la valeur obtenue en incluant l’objet i ou en excluant cet objet.
3. Reconstruction de la Solution : À partir de la table remplie, reconstruire la
solution optimale en déterminant quels objets ont été inclus dans le sac à dos.

L’implémentation concrète de cet algorithme peut varier en fonction des détails de

la programmation et du langage utilisé.

0.5.4 Complexité Temporelle

La complexité temporelle de l’algorithme de programmation dynamique pour le pro-
blème de sac à dos dépend principalement du remplissage de la table. La taille de la table
est O(n×W ), et pour chaque cellule, les calculs nécessitent un temps constant.

Ainsi, la complexité temporelle totale est généralement de l’ordre de O(n×W ). Cette

complexité est beaucoup plus efficace que d’autres approches, telles que la recherche
exhaustive, qui ont une complexité exponentielle.

Il est important de noter que cette complexité peut être acceptable pour des instances
de problèmes de taille modérée, mais elle peut devenir prohibitivement élevée pour des
instances plus grandes. Dans de tels cas, des techniques d’optimisation ou d’autres va-
riantes de l’algorithme peuvent être envisagées.

13
0.6. MODÈLES DE CHEMINS : ÉQUATION DE RÉCURRENCE ET
ALGORITHME
0.6 Modèles de chemins : équation de récurrence et
algorithme
Equation de Bellman dans un graph sans circuit
�
On suppose un graphe pondéré dirigé, étiqueté G = (V, E) où V représente les sommets
et E représente les arêtes du graphe. Le graphe se compose de sept sommets étiquetés A,
B, C, D, E, F et G.

Le graphe est lié à un algorithme informatique, démontrant le calcul du chemin le plus

long ou l’accumulation de poids, comme l’indiquent les opérations « max » écrites sur
certaines arêtes.

f (u) : valeur du plus long chemin de s à u Complexité : O(|E|)

f (v) = max(f (u) + wuv ) ∀v ∈ V \ {s}
u|(u, v) ∈ E u prédecesser de v
f (s) = 0

14
0.6. MODÈLES DE CHEMINS : ÉQUATION DE RÉCURRENCE ET
ALGORITHME

Vous pouvez observer qu’il existe des nœuds étiquetés avec des paires de nombres
(comme ”0,0”, ”1,0”, ”2,1”, etc.), et ces nœuds sont disposés en niveaux ou couches de
gauche à droite. Chaque nœud est connecté à un ou plusieurs nœuds de la couche suivante
par des bords dirigés représentés par des flèches. Il y a un nœud spécial appelé « s » à
l’extrême gauche, qui désigne généralement la source ou le point de départ. À l’extrême
droite, il y a un autre nœud spécial appelé « t », qui représente généralement la cible ou
le point final.

f ∗ (C, i) = max(f ∗ (C − Wi , i − 1) + vi , f ∗ (C, i − 1)) ∀i = 1, . . . , n ∀C ≥ wi

f ∗ (C, 0) ∀C ≥ 0

f ∗ (C, i) = f ∗ (C, i − 1) ∀C < Wi ∀i = 1, . . . , n

15
0.6. MODÈLES DE CHEMINS : ÉQUATION DE RÉCURRENCE ET
ALGORITHME
f ∗ (C, i) = max(f ∗ (C − Wi , i − 1) + vi , f ∗ (C, i − 1)) n = 5 W = 10

v1 v2 v3 v4 v5 w1 w2 w3 w4 w5
� �
3 5 6 7 10 2 3 4 4 8

Données : n, W, (v1 ..., vn ), (w1 ..., wn )

Sortie : la valeur d’un sac optimal
Soit f une matrice de dimentions (W + 1)x(n + 1)
f [C, i] = 0 ∀C = 0, ..., W, ∀i = 0, ..., n
POUR TOUT i de 1 à n :
POUR TOUT C de 0 à W :
SI Wi ≤ C :
f [C, i] = max(f [C − wi , i − 1] + vi , f [C, i − 1])
SINON :
f [C, i] = f [C, i − 1]
RETOURNER f [W, n]

wi 0 2 3 4 4 8
vi 0 3 5 6 7 10
c|i 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 0 0 0 0 0
2 0 3 3 3 3 3
3 0 3 5 5 5 5
4 0 3 5 6 7 7
5 0 3 8 8 8 8
6 0 3 8 9 10 10
7 0 3 8 11 12 12
8 0 3 8 11 13 13
9 0 3 8 14 15 15
10 0 3 8 14 16 16

16
0.6. MODÈLES DE CHEMINS : ÉQUATION DE RÉCURRENCE ET
ALGORITHME
POUR TOUT i de 1 à n :
POUR TOUT C de 0 à W :
SI Wi ≤ C :
SI f [C − wi, i − 1] + vi ≥ f [C, i]
p[C, i] = C
SINON : p[C, i] = C
f [C, i] = max(f [C − wi , i − 1] + vi , f [C, i − 1])
SINON Wi ≤ C :
p[C, i] = C
f [C, i] = f [C, i − 1]

wi 0 2 3 4 4 8
vi 0 3 5 6 7 10
C�i 0 1 2 3 4 5
0 -1 0 0 0 0 0
1 -1 1 1 1 1 1
2 −1 0 2 2 2 2
3 −1 1 0 3 3 3
4 −1 2 1 0 0 4
5 −1 3 2 5 5 5
6 −1 4 3 2 2 6
7 −1 5 4 3 3 7
8 −1 6 5 4 4 8
9 −1 7 6 5 5 9
10 −1 8 7 6 6 10

La matrice p est analogue aux prédécesseurs dans l’algorithm de Bellman-Ford et

permet de retrouver une solution optimal

Algorithme récursif

17
0.7. CONCLUSION

0.7 Conclusion
La résolution du problème du sac à dos à travers l’application de l’algorithme de program-
mation dynamique a démontré son efficacité dans la recherche de solutions optimales. À
travers cette étude de cas spécifique, nous avons exploré les aspects fondamentaux du
problème, formulé une approche algorithmique, et implémenté cette dernière pour une
application pratique liée à la gestion d’un sac à dos de voyage.

L’algorithme de programmation dynamique a permis une optimisation remarquable, maxi-

misant la valeur totale des articles inclus dans le sac à dos tout en respectant la contrainte
de poids imposée. Les résultats obtenus ont démontré la puissance de cette approche pour
résoudre des problèmes d’optimisation complexes, offrant une solution efficiente et évo-
lutive.

Cependant, il est essentiel de souligner que la performance de l’algorithme peut être in-
fluencée par la taille du problème et la capacité du sac à dos. Des instances de problèmes
plus importantes peuvent nécessiter des adaptations ou des améliorations de l’algorithme
pour maintenir une efficacité pratique.

En conclusion, l’étude de cas a fourni un aperçu concret de la manière dont la program-

mation dynamique peut être appliquée avec succès pour résoudre des problèmes de sac à
dos spécifiques. Cette approche offre une solution robuste et efficace qui peut être étendue
à une variété d’applications dans des domaines tels que la logistique, la finance, et la pla-
nification de projet. La programmation dynamique, en tant que méthode algorithmique,
continue de jouer un rôle central dans la résolution de problèmes complexes et demeure
une ressource précieuse pour les professionnels de l’informatique et les chercheurs en op-
timisation.

18