Discussion :

[olibara]

Bonjour
J'ai un problème d'affectation un peu particulier
Je dispose d'une liste de N soldes débiteurs (15 montants) : total 1880
J'ai une autre liste de 29 payements : total 1880
Les 29 payements couvrent donc les soldes débiteurs

Mais j'aimerais trouver l'algorithme qui me permettrait dans ce type de situation d'affecter au mieux les payements afin de couvrir correctement les soldes
Ça pourrait ressembler a un Algorithme de Kuhn, mais je ne vois pas bien comment l'aborder dans le cas présent

Merci pour votre aide

[Flodelarab]

Bonjour

d'affecter au mieux les payements

Que signifie "au mieux" ?

[olibara]

Au mieux signifie qu’idéalement TOUS les payements devraient couvrir les Soldes
Mais si je ne répartis pas biens les affectation je vais avoir des payement non affecté

Exemple simple
3 Solde : 5, 10 et 25
4 Payements : 10, 10, 10, 5 et 5

Si j'affecte les deux payement de 5 pour couvrir le solde de 10 il deviendra impossible de couvrir correctement les soldes de 5 et 25

[anapurna]

salut

je pense qu'il veut lettré ses payement sur les solde existant
tes solde doivent être constitué de facture c'est sur eux que le lettrage doit se faire
le solde n'est que la résultante des facture moins les régularisation effectué (avoir,payement,OD,... )

Petite question est ce que la répartition des payements est exact ?

1°) cas ou la somme de certain payements corresponde a un solde unique
un exemple

Pour les payements
50
75
15
et Pour les soldes
75
65
le résultat seras donc
75 -> 75
50+15 -> 65
2°) cas ou les solde ne correspondent pas exactement a une somme de payement
Un exemple on as toujours
en payement
50
75
15
mais pour les soldes
80
60

donc l'affectation seras
80-(75+50) =-45
60-(45+15) = 0

Pour affecter tes payements au solde
le plus simple est de le trié du plus gros au plus petit et tu retire les éléments pouvant être le constituant du solde

@+ Phil

[olibara]

Merci Anapurna

Tu a bien exposé les cas possible et a priori je ne sais pas si on est dans le cas idéal ou ton cas N°2 (c'est pour cela que j'avais fait l’assertion "Au Mieux"
La solution de tri est évidement celle qui vient rapidement a l'esprit mais je ne suis pas convaincu qu'elle permet de résoudre "Au Mieux" le problème

Comme je le disait, cela ressemble a un problème d'affectation tel que décrit dans algorithme "Hongrois" méthode du Kuhn

Mais entre la ressemblance et la mise en oeuvre il y a une marge...
Donc j'appelle à l'aide :-)

[anapurna]

salut

la methode decrit seras sans null doutes selons le cas le au mieux
avec une petite variante pour le cas deux ou tu peut deja pour chaque somme
chercher la valeur maximal possible a déduire et la seconde passe peut compléter le reste

Je resume ma premier boucle installe le payement entier pour chaque solde
la deuxième fait le complément avec les restes .. il n'y a pas plus simple

cela ressemble au problème du sac a dos

[olibara]

Merci Anapurna
Oui ca ressemble au sac a dos
Et dans la pratique a un tetris


Mais je ne suis pas convaincu que ta méthode en deux passe puisse toujours trouver la meilleure solution
Il me semble que dans certains cas une affectation de première passe devrait plutôt être remplacée par une sommation d’éléments : Ce sont des cas d'affectation que devrait pouvoir (a mon avis) résoudre l’algorithme de Kuhn

Mais d'une part je ne maîtrise pas vraiment cet Algorithme et d'autre part je n'ai pas encore non plus bien conceptualisé comment je pourrais l'appliquer ici

Je vais quand même essayer ta solution simple en deux boucles ne fut-ce que pour avoir une idée du résultat