algorytm określający minimalne płatności w grupie
Problem
Niedawno poproszono mnie o obliczenie należnych pieniędzy w grupie ludzi, którzy wyjechali razem na wycieczkę i natrafiłem na interesujący problem: biorąc pod uwagę, że znasz kwoty, które każda osoba jest winna innemu, jaki jest ogólny algorytm konsolidacji długów między ludźmi tak, że tylko minimalna liczba płatności musi być dokonana? Weź to jako przykład:
Mike jest winien Johnowi 100John jest winien Rachel 200Mike jest winien Rachel 400Możemy usunąć płatność między Mikiem i Johnem, zmieniając dług w ten sposób:
Mike jest winien Johnowi 0John jest winien Rachel 100Mike jest winien Rachel 500Zrobiłem matematykę ręcznie, ponieważ było to dość łatwe, ale wtedy programista we mnie pragnął znaleźć ogólny algorytm, aby zrobić to dla arbitralnie dużej grupy. Wydaje mi się to algorytmem graficznym, więc przeformułuję to jako wykres:
Oglądane jako wykresWierzchołki to ludzie w grupieKrawędzie są kierowane i ważone kwotą należną. Na przykład przewaga od Mike'a do Rachel z wagą 500 oznacza, że Mike jest winien Rachel 500.Ograniczenie: suma netto wag dla każdego węzła musi pozostać niezmieniona.Celem jest znalezienie wykresu z minimalną liczbą krawędzi, które nadal spełniają ograniczenie.