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

Algorithmes et structures de données Discussion :

Automatisation de recherche de correspondance entre montants détaillés et regroupés


Sujet :

Algorithmes et structures de données

  1. #1
    Pgs
    Pgs est déconnecté
    Membre régulier
    Profil pro
    Inscrit en
    avril 2004
    Messages
    469
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2004
    Messages : 469
    Points : 99
    Points
    99
    Par défaut Automatisation de recherche de correspondance entre montants détaillés et regroupés
    Bonjour,
    Je dispose d'une liste d'articles avec, pour chaque article, un montant total de dépenses (en euros avec centimes).
    Je dispose d'une seconde liste correspondant à un regroupement, par famille d'articles, des montants de la liste précédente.
    Je ne connais pas la correspondance entre les articles et les familles d'articles.
    Je cherche à élaborer un algorithme qui retrouve cette correspondance entre les montants et leurs regroupements (ou propose plusieurs correspondances si, par coïncidence, au centime près, plusieurs configurations de regroupement peuvent être obtenues).
    Merci par avance pour toute aide.

  2. #2
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    25 868
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 25 868
    Points : 181 508
    Points
    181 508
    Par défaut


    Ton problème me rappelle ceci : https://xkcd.com/287/

    Sinon, ne s'agirait-il pas d'un problème de sac à dos, en prenant les valeurs égales aux poids et la capacité du sac égale au montant à obtenir ? Dans ce cas, puisque tu sais d'avance qu'il y a moyen de combiner les items pour remplir le sac exactement à sa capacité, tu devrais y arriver. https://fr.wikipedia.org/wiki/Probl%...sac_%C3%A0_dos

    Plus précisément, je vois deux manières d'aborder le problème.
    1. Comme un bourrin : tu considères qu'il y a un sac à dos par groupe, tu utilises un algorithme pour tous les sacs d'un coup. https://developers.google.com/optimi...tiple_knapsack. Tu peux aussi regarder du côté du bin packing, ce n'est qu'une généralisation du sac à dos.
    2. Plus finaud : tu considères un premier montant total comme un sac à dos, tu y fais rentrer un maximum de choses ; pour le deuxième groupe, tu fais de même, mais en enlevant les items déjà placés quelque part. Pour l'implémentation, regarde la programmation dynamique, c'est extrêmement efficace en pratique ()https://fr.wikipedia.org/wiki/Probl%...tion_dynamique.
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Pgs
    Pgs est déconnecté
    Membre régulier
    Profil pro
    Inscrit en
    avril 2004
    Messages
    469
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2004
    Messages : 469
    Points : 99
    Points
    99
    Par défaut
    Merci à toi pour tous ces éléments (pas mal, le "comic" du resto !).
    Tes réponses sont toutefois très avancées par rapport à mon niveau dans le domaine (niveau amateur -).
    Mais je vais essayer de les comprendre.
    En attendant, et sachant que je suis dans le cas particulier où chaque contenant correspond à une somme exacte d'éléments, un schéma maxi bourrin pourrait-il être de :
    a) Prendre un premier total et tester toutes les combinaisons d'éléments jusqu'à tomber sur une qui matche et la mémoriser
    b) Faire ainsi de suite avec chaque total et les éléments restants.
    Resterait à traiter le cas où au moins un total correspond par coïncidence à plusieurs sous-ensembles...
    Défendable ?
    Si oui quel pourrait être un bon algorithme pour l'étape a) ?

  4. #4
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherche
    Inscrit en
    août 2008
    Messages
    25 868
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 25 868
    Points : 181 508
    Points
    181 508
    Par défaut
    Citation Envoyé par Pgs Voir le message
    Si oui quel pourrait être un bon algorithme pour l'étape a) ?
    Programmation dynamique pour du sac à dos ? Dans ton cas, je ne crois pas aux algorithmes approchés (genre trier les items et les prendre dans cet ordre), puisque tu as vraiment besoin d'obtenir une combinaison exacte, qui atteint exactement la bonne somme.
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Pgs
    Pgs est déconnecté
    Membre régulier
    Profil pro
    Inscrit en
    avril 2004
    Messages
    469
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : avril 2004
    Messages : 469
    Points : 99
    Points
    99
    Par défaut
    Merci, je vais me pencher sur la programmation dynamique (je ne connaissais même pas ce nom !)
    Bonne journée

Discussions similaires

  1. Réponses: 3
    Dernier message: 07/10/2017, 20h49
  2. Réponses: 2
    Dernier message: 13/07/2017, 11h28
  3. correspondance entre noms (bases et tables) et répertoires
    Par Eärendil dans le forum PostgreSQL
    Réponses: 2
    Dernier message: 03/05/2005, 15h21
  4. recherche composant hybride entre le ComboBox et le DBLookup
    Par Calixte dans le forum Bases de données
    Réponses: 3
    Dernier message: 14/06/2004, 14h32

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