Как упрощение долгов минимизирует переводы
После записи расходов калькулятор превращает запутанный клубок долгов в минимально возможное число платежей. Этот приём называется упрощением долгов (debt simplification).
1. Рассчитать чистый баланс каждого
Для каждого человека вычитаем то, что он должен (его долю в каждом расходе), из того, что он заплатил. Положительный баланс означает, что ему должны; отрицательный — что должен он.
2. Сопоставить крупнейшего должника с крупнейшим кредитором
Тот, кто должен больше всех, сопоставляется с тем, кому должны больше всех. Один перевод погашает максимум обоих балансов.
3. Повторять, пока все не выйдут в ноль
После каждого сопоставления меньший баланс гасится и удаляется, затем переходим к следующей паре. Этот жадный подход гарантирует минимальное число переводов.