Bonjour à toutes et tous,


Petite question postée en conséquence de l'absence de résultats de recherche vraiment fiables ici ou ailleurs...

J'élabore actuellement un programme qui doit, sur la base d'un listing d'écritures comptables pour un client donné, rapprocher les écritures entre elles par montant afin de les lettrer (règles connues du lettrage comptable, rien de plus, mais de façon automatisée)

Lorsque les relations se font en 1 pour 1, aucun problème : 100 euros au débit rapprochés de 100 euros au crédit = match = lettrage.
Sauf que potentiellement bien entendu, il y a N écritures au crédit à rapprocher avec N écritures au débit. Par exemple :

Débit Crédit
50
50
50
100
50
200

Cette liste pourrait donner lieu au lettrage de toutes les lignes sauf la dernière qui ne serait pas considérée (150 d'un côté, 150 de l'autre)
Les combinaisons n'auraient pas de priorité, peu importe ce qu'on lettre du moment qu'on a l'équilibre.

J'ai lu un peu de littérature d'algo, dont celle du "Knapsack problem" mais elle ne me semble pas appropriée car là l'idée c'est bien d'avoir un match complet.

Avez-vous déjà été confrontés à la question ? Des suggestions ? Des snippets de code ou d'algo ?

Merci pour vos suggestions