The Problem

Меня недавно попросили подсчитать деньги, причитающиеся среди группы людей, которые вместе отправились в поездку и столкнулись с интересной проблемой: учитывая, что вы знаете суммы, которые каждый должен другому, каков общий алгоритм консолидации долгов между людьми так что нужно сделать только минимальное количество платежей? Возьмите это как пример:

Mike owes John 100 John owes Rachel 200 Mike owes Rachel 400

Мы можем удалить платеж между Майком и Джоном, переформулировав долги следующим образом:

Mike owes John 0 John owes Rachel 100 Mike owes Rachel 500

Я делал математику вручную, потому что это было достаточно легко, но потом программисту во мне не терпелось найти общий алгоритм, чтобы сделать это для сколь угодно большой группы. Мне кажется, что это графический алгоритм, поэтому я переформулирую это как график:

Viewed as a Graph The vertices are the people in the group The edges are directed and weighted by the amount owed. For example, an edge from Mike to Rachel with weight 500 means that Mike owes Rachel 500. Constraint: the net sum of weights for each node must remain unchanged. The goal is to find a graph with the minimum number of edges that still satisfy the constraint.