Das Problem

Vor kurzem wurde ich gebeten, die Schulden einer Gruppe von Personen zu berechnen, die gemeinsam verreist sind und auf ein interessantes Problem gestoßen sind: Wenn Sie die Beträge kennen, die jede Person einer anderen schuldet, ist dies ein allgemeiner Algorithmus zur Konsolidierung der Schulden zwischen Personen damit nur die minimale Anzahl von Zahlungen geleistet werden muss? Nehmen Sie dies als Beispiel:

Mike schuldet John 100John schuldet Rachel 200Mike schuldet Rachel 400

Wir können eine Zahlung zwischen Mike und John entfernen, indem wir die Schulden wie folgt umformulieren:

Mike schuldet John 0John schuldet Rachel 100Mike schuldet Rachel 500

Ich habe die Berechnung von Hand gemacht, da es einfach genug war, aber der Programmierer in mir wollte unbedingt einen allgemeinen Algorithmus finden, um dies für eine beliebig große Gruppe zu tun. Dies scheint mir ein Graph-Algorithmus zu sein, also werde ich dies als Graph umformulieren:

Als Grafik betrachtetDie Eckpunkte sind die Personen in der GruppeDie Kanten werden nach dem geschuldeten Betrag gerichtet und gewichtet. Zum Beispiel bedeutet eine Kante von Mike zu Rachel mit einem Gewicht von 500, dass Mike Rachel 500 schuldet.Einschränkung: Die Nettogewichtsumme für jeden Knoten muss unverändert bleiben.Ziel ist es, ein Diagramm mit der Mindestanzahl von Kanten zu finden, die die Bedingung noch erfüllen.