Discussion :

[nico1492]

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

[MABROUKI]

bonjour

Algo du flot maximum dont l'algo de Ford-Fulkerson est une variante peut être une bonne piste.
flot maximum ici:
https://fr.wikipedia.org/wiki/Probl%...C3%BBt_minimum

Ford-Fulkerson ici:


https://fr.wikipedia.org/wiki/Algori...Ford-Fulkerson

[nico1492]

Merci, j'avais zappé la réponse mais bien repris les éléments !

Mieux vaut tard que jamais...