Le problème du sac à dos est un problème d'optimisation combinatoire NP-difficile, ce qui signifie que nous ne connaissons pas d'algorithme polynomial permettant de le résoudre. Cependant, il existe en pratique des algorithmes donnant de très bons résultats.
Nous nous intéressons dans cet article au comportement d'un compilateur face à la résolution d'un tel problème. Pour cela, nous implémentons deux algorithmes en n'utilisant que des techniques de méta-programmation. En pratique, cela signifie que nous allons écrire les données du problème dans le code, puis que nous laisserons au compilateur le soin de sa résolution.
La première partie de cet article introduit le problème. Elle est suivie par la deuxième section dans laquelle un algorithme naïf ainsi qu'une technique de programmation dynamique sont décrits et implémentés de manière classique. La troisième section présente des techniques de méta-programmation et montre ensuite les patrons de classe permettant la résolution lors de la compilation en utilisant l'un des deux algorithmes. Enfin, la dernière partie concerne la comparaison des performances obtenues avec chacune des ces approches.
Résolution de problèmes de sac à dos par méta-programmation
Répondre avec citation
A méditer: La solution la plus simple est toujours la moins compliquée
. Sa fait plaisir de voir un peu de MP ici 
.
Partager