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
    Membre régulier
    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



    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
    Membre régulier
    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

    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
    Membre régulier
    Merci, je vais me pencher sur la programmation dynamique (je ne connaissais même pas ce nom !)
    Bonne journée

###raw>template_hook.ano_emploi###