Discussion :

[Pgs]

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.

[dourouc05]

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.

[Pgs]

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) ?

[dourouc05]

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.

[Pgs]

Merci, je vais me pencher sur la programmation dynamique (je ne connaissais même pas ce nom !)
Bonne journée