Autour d'un café....

[tiboel]

Bonjour,

je me pose une question simple. Je cherche à résoudre un petit problème mathématique du quotidien. Soit un groupe d'amis qui paie une somme X, comment trouver qui doit quoi à qui (si on partage l'addition) afin de minimiser le nombre de transactions ?

Je cherche un algo simple à mettre en place avec pour données initiales seulement le montant des dépenses de chacun.

Merci

Thibaud

[Imod]

Il me semble que Muriel Robin pourrait te donner quelques idées :we:

Imod

[mathelot]

bjr,

ils ont tous payé la somme moyenne.
relativement à chaque addition particulière, certains ont trop payé
et d'autres pas assez. Il semble qu'il faille éviter les "rompus"
ie, regrouper deux crédits de 4,21 et 2,31 avec un débit de 6,52,
donc essayer de grouper des montants qui vont ensemble ???

déja, on peut considérer, en comptant en centimes, que c'est un problème d'arithmétique (avec entiers relatifs)

[Patastronch]

C'est un probleme de flot dans un graphe (on peut aussi l emodeliser sous forme d'un graphe multicritere et faire ensuite un plus court chemin). On est tombé sur le probleme avec d'autres chercheurs, et c'était drole de vori comment chacun cherchait a modeliser le probleme dans sa spécialité pour trouver le nombre de transactions minimal :)