IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

Résolution de problèmes de sac à dos par méta-programmation


Sujet :

C++

  1. #1
    Membre confirmé

    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    104
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 104
    Points : 614
    Points
    614
    Par défaut Résolution de problèmes de sac à dos par méta-programmation
    Bonjour,

    Je vous propose un nouvel article sur la résolution de problèmes de sac à dos à la compilation en utilisant des techniques de méta-programmation.

    Le synopsis est le suivant :
    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.
    N'hésitez pas à laisser vos remarques et suggestions dans ce fil de discussion.

    Merci

  2. #2
    Expert éminent sénior
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 612
    Points : 30 611
    Points
    30 611
    Par défaut
    Bravo pour le travail
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  3. #3
    Membre chevronné
    Avatar de Goten
    Profil pro
    Inscrit en
    Juillet 2008
    Messages
    1 580
    Détails du profil
    Informations personnelles :
    Âge : 33
    Localisation : France

    Informations forums :
    Inscription : Juillet 2008
    Messages : 1 580
    Points : 2 205
    Points
    2 205
    Par défaut
    Pareil, bravo . Sa fait plaisir de voir un peu de MP ici .
    "Hardcoded types are to generic code what magic constants are to regular code." --A. Alexandrescu

Discussions similaires

  1. Résolution du problème du sac-à-dos quadratique en variables bivalentes
    Par nounou88 dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 16/01/2012, 14h55
  2. Compréhension d'un algorithme sur le problème du sac à dos
    Par Treuze dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 18/12/2006, 16h26

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo