Как я схлопнул 14 переводов в 5: бот для дележа расходов на голом Node без единой зависимости

[wataru]

Дальше жадный алгоритм: берём самого большого должника и самого большого кредитора, закрываем меньшую из двух сумм, повторяем.

Не обязательно брать максимальных. Общее количество переводов почти всегда равно количеству кредиторов + количеству должников. За один перевод один из двух участников закрывает долг или недостатчу и выходит из расмотрения.

Меньше переводов получится, только если сумма остаточного долга равна кредиту и за один перевод выбывают 2 человека.

Минимизировать количество перводов тут - NP-полная задача. Она эквивалентна разбиению множества коредиторов и должников на подмножества с нулевой суммой.

Можно решить это за O(N 2^N) динамическим программированием по маске. Для 20 человек еще можно это дело посчитать довольно быстро, для 40 уже почти никак.

Хотя в среднем, жадный алгоритм наверно искоючит ситуацию, когда один человек получает много переводов от других.