Salut à tous,
j’aimerai programmer (au final en PHP+MySQL) une méthode pour optimiser un remboursement.
Au départ il y a des requetes, par exemple : A demande de se faire rembourser 1 par B et 1 par C, ainsi on a un tableau de remboursement de type :
|---------on leur doit de l’argent
v
x A B C <------ ils doivent cet argent
A x 1 1
B x x 0
C x x x
si en plus on ajoute la requete : B doit 1 à C alors on a :
x A B C
A x 1 1
B x x -1 (oui on a besoin que de la moitié du tableau avec les nombre relatifs)
C x x x
mais au final
…A
^ ^
1 | \ 1
B->C
…1
peut etre simplifier en : B doit 2 à A
Et ma question est donc, quel est l’algorithme que peu optimiser ces échanges, et pour ceux qui connaissent est-ce que l’algorithme du simplexe peut etre utilisé ici ?
moi j’ai gerer les compte pendant les vacances lol
il faut gerer 1 valeur par personne sont solde cad dire ce qu’il doit moins ce qu’on lui doit…
donc la personne est en negatif si on lui doit des sous et en positif si elle en doit…
tu obtient un vecteur (associatif) qu’il faut trier dans l’ordre des valeurs dus…
ensuite tu part du mec à qui on doit le plus et pour ce mec tu va chercher la personne qui doit le plus et tu voit si on peut faire un remboursement partiel ou total… si c un remboursement total ok tu note le remboursement et tu soldes les comptes,
si c partiel tu note le remboursement tu solde partiellement et tu passe a la deuxieme personne qui doit le plus pour rembours
ex
A -50
B -30
C -10
D 10
E 20
F 30
G 30
on commence par A
G donne 30 à A (partiel)
A -20
B -30
C -10
D 10
E 20
F 30
G 0 (effacé du vecteur)
F donne 20 à A (total)
A 0 (effacé)
B -30
C -10
D 10
E 20
F 10
on passe à B et on recommence !
le seul desaventage c qu on perd la notion qui doit a qui
ps peut etre qu il faudra gerer des cas plus compliqué quand y a des grosse somme et des toute petites à 9 h 00 du mat je voit pas trop les effets de bord …
Le probleme c’est que je dois gerer les remboursements de toutes c personnes, et donc enregistrer ce qu’ils se doivent entre eux. Mais le truc ce de minimiser les échange, il faut qu’il y ait le plus de 0, et dans l minimisation le risque c de tourner en rond, et la je sais meme pas comment commencer.
avec l’algo que je propose on perd la notion de ce que devait qui a qui a l’origine mais on gagne la notion de ce que doit qui a qui optimisé pour qu’il y ai le moins de transaction…
pourquoi gerer un tableau a 2 dimensions ???
maintenant si il faut absolument garder l’historique des dettes… c sur c plus complex mais dans ce cas optimisation et historique me semble antinomique
