Discussion :

[fluminis]

Bonjour à tous,

Je cherche un algo mais je ne sais pas dans quelle direction chercher.

Voila, mon probleme est le suivant :

Il y a N amis qui sont partis en voyage. Ils ont tour à tour payé pour les autres.
Le voyage se termine et je cherche à calculer qui doit combien et surtout à qui ils doivent e l'argent.

Savoir combien chacun à payé, ca c'est ok.
Savoir combien chacun aurait du payé, c'est ok.
Savoir combien chacun doit, c'est simplement : combien il aurait du payer - combien il a payé. (si c'est negatif, il doit recevoir de l'argent)
Savoir combien chacun doit recevoir, c'est simplement : - combien il doit. (si négatif, il ne doit rien recevoir)

Donc avec tous ces chiffres en main, je cherche comment limiter les échanges d'argent entre chaque participant pour solder les comptes. Histoire que chaque participant fasse le moins de cheque possible à ses copains.

Ce problème semble assez classique et il existe peut-etre des algorithmes en théorie des graphes qui pourraient répondre à ca...
Est-ce que vous voyez ce que je veux faire ? Avez-vous un idée d'algo existant qui pourrait me convenir ?

Bonne fin de weekend

Fluminis

Exemple :
Rémi : à payé 120€, aurait du payer 90€, doit recevoir 30€
Stef : à payé 70€, aurait du payer 10€, doit recevoir 60€
Mélanie : à payé 0€, aurait du payer 90€, doit 90€

Au final, dans ce cas simple il n'y a qu'une solution (melanie donne a remi 30 et à stef 60), mais dès qu'il y a plus de participants, c'est plus dificile de savoir qui doit donner à qui.

[Invité]

Bonjour,
J'ai déjà résolu ce problème pour régler les comptes de succession entre frères et soeurs, je n'ai pas été chercher d'algorithme particulier, c'est pas vraiment difficile.
Evidemment pour un nombre quelconque de membres c'est plus compliqué. Par exemple, vous pouvez écrire les équations linéaires. Il est probable qu'il en manque une, puisqu'à priori il y a plusieurs solutions, il suffit peut-être d'écrire que la somme des carrés des échanges est minimum.
Bon courage.

[pseudocode]

D'accord avec Pierre Dolez.

Si on note MR le flux d'argent entre Mélanie et Rémie, RS flux d'argent entre Rémi et Stef, ... on peut écrire que:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
RM+RS=0   // flux sortant pour Remi
MR+SR=30  // flux entrant pour Remi
 
SM+SR=0   // flux sortant pour Stef
MS+RS=60  // flux entrant pour Stef
 
MR+MS=90  // flux sortant pour Melanie
RM+SM=0   // flux entrant pour Melanie

Reste à modéliser la contrainte de "transfert d'argent minimum".