Есть скучная бытовая задача: компания скидывается на общее — поездку, дачу, ужин, — кто-то платит за всех, и в конце надо свести, кто кому сколько должен. Её отлично решает Tricount, но у него есть трение: отдельное приложение, которое надо ставить и куда надо заводить друзей. А друзья и так все в Telegram.
Поэтому я сделал независимый аналог как Telegram Mini App — ««Сочтёмся»»: открывается внутри мессенджера, авторизация бесшовная, пригласить человека — просто кинуть ссылку в чат. И вот на, казалось бы, чисто арифметической мелочи — свести балансы к переводам «кто кому сколько» — я неожиданно упёрся в честную NP-трудную задачу. Разбор этой одной проблемы и её решения — дальше.
Двадцать строк, которые «просто работают»
Смотрите, как это устроено. У каждого участника есть баланс: сколько он в сумме заплатил минус его доля во всех тратах. Кто-то в плюсе (ему должны), кто-то в минусе (должен он). Сумма всех балансов, разумеется, ноль — сколько денег кому-то недостаёт, ровно столько у кого-то лишних.
Дальше надо превратить балансы в переводы. Первое, что приходит в голову — жадность: берём самого большого должника и самого большого кредитора, гасим между ними сколько можем, повторяем. Десять строк:
def greedy_transfers(balances): deb = sorted(b for b in balances if b < 0) # должники, по возрастанию cred = sorted((b for b in balances if b > 0), reverse=True) # кредиторы, по убыванию di = ci = t = 0 while di < len(deb) and ci < len(cred): pay = min(-deb[di], cred[ci]); t += 1 deb[di] += pay; cred[ci] -= pay if deb[di] == 0: di += 1 if cred[ci] == 0: ci += 1 return t
Работает, отдаёт разумные переводы, поехало в прод. Живёт себе. Ровно до того дня, когда я от нечего делать засмотрелся на один конкретный расклад.
«Стоп, а это вообще оптимально?»
Вот балансы пяти человек (в рублях, для наглядности): +3, +1, −4, +2, −2.
Мой жадный алгоритм делает так: берёт самого большого должника (−4) и гасит его против самого большого кредитора (+3) — перевод на 3, остаётся −1. Дальше эта −1 идёт к +2, потом −2 разбивается на кусочки… в итоге четыре перевода.
А теперь посмотрите глазами. Тут же есть очевидная пара: +2 и −2 — они рассчитываются одним переводом и забывают друг о друге. Остаётся +3, +1, −4 — а это тоже замкнутая компания, её гасят двумя переводами (−4 отдаёт 3 и 1). Итого — три перевода, а не четыре.
Жадность не увидела, что группу можно разбить на две самодостаточные «компании», внутри которых всё сходится в ноль. И тут до меня дошло, в чём вообще задача.
Ключевая идея: искать «нулевые компании»
Переформулируем. Если какая-то группа людей в сумме должна сама себе ноль — их можно рассчитать отдельно, ни с кем снаружи не связываясь. Компанию из k человек с нулевым балансом всегда можно закрыть k−1 переводами (это ровно тот же жадный проход, но внутри группы).
Значит, если мы разобьём всех m участников с ненулевым балансом на g таких нулевых компаний, суммарно понадобится
(k₁−1) + (k₂−1) + … = m − g переводов.
Вывод, который переворачивает задачу с ног на голову: чтобы сделать переводов поменьше, надо разбить людей на как можно большее число нулевых компаний. Минимум переводов равен m − g*, где g* — максимальное число таких компаний в разбиении.
Это не эвристика и не «на глаз» — это точная формула оптимума. (Строгое доказательство короткое: с одной стороны, любое разбиение на g компаний даёт план в m − g переводов; с другой — если нарисовать граф, где ребро — перевод, то в оптимальном плане каждая компонента связности обязана суммироваться в ноль, а значит компонент не больше g*, и рёбер в графе не меньше m − g*. Отсюда равенство.)
Красиво. Осталось найти это максимальное разбиение — и я полез писать алгоритм. Тут-то и поджидала засада.
Почему нет простого оптимального алгоритма
Чтобы разбить на максимум нулевых компаний, надо хотя бы уметь находить непустую подгруппу, которая суммируется в ноль.
Вспомним классику — задачу о сумме подмножеств (Subset-Sum): даны числа, надо узнать, набирается ли из какого-то их подмножества заданная сумма. Она NP-полна — одна из хрестоматийных трудных задач из списка Карпа 1972 года (в оригинальном списке она фигурирует под именем Knapsack).
Свести её к нашей — дело нескольких строчек. Пусть даны положительные a₁,…,aₙ и цель t, и мы хотим узнать, набирается ли t из какого-то подмножества. Соберём из этих чисел балансы: сами a₁,…,aₙ, плюс два «замыкающих» участника с балансами −t и −(Σaᵢ − t). Всё вместе даёт ноль — корректный расклад для нашего приложения. И теперь нетривиальная нулевая компания в этих балансах существует ровно тогда, когда какое-то подмножество aᵢ даёт в сумме t. Интуиция простая: чтобы занулить −t, к нему нужно добрать aᵢ ровно на t — вот вам и Subset-Sum. (Строго говоря, остаётся ещё случай с элементом −(Σaᵢ − t), но он сводится к тому же вопросу через дополнение подмножества.)
То есть если бы у меня был быстрый способ находить оптимальное разбиение на нулевые компании — я бы им заодно решал Subset-Sum за полином, а так никто не умеет. Минимизация числа переводов NP-трудна. В литературе, кстати, она известна под именем Optimal Account Balancing — так что об эту задачу спотыкаюсь не я первый.
Осознание было двойственное. С одной стороны — обидно: «поделить счёт» внезапно оказалось не проще, чем взлом рюкзачных шифров. С другой — приятно: моя двадцатистрочная функция, оказывается, флиртует с P ≟ NP.
Что делать: считать точно, но по подмножествам
NP-трудность означает, что универсального быстрого алгоритма нет. Но она ничего не говорит про мои конкретные входные данные. А они — крошечные: это дружеская компания, а не биржа. Людей с ненулевым балансом там от силы десяток.
А когда данных мало, экспонента перестаёт быть страшной. Раз задача про подмножества — будем и считать по подмножествам, динамикой по битовым маскам. Для каждого подмножества M храним dp[M] — максимальное число нулевых компаний, на которые его можно разбить. Тогда
dp[M] = max(dp[M без P] + 1) по всем непустым нулевым подмножествам P ⊆ M,
а ответ — m − dp[всё множество].
def min_transfers(balances): v = [b for b in balances if b != 0] m = len(v) N = 1 << m subset_sum = [0] * N # сумма балансов в каждом подмножестве for M in range(1, N): low = M & (-M) subset_sum[M] = subset_sum[M ^ low] + v[low.bit_length() - 1] dp = [-1] * N dp[0] = 0 for M in range(1, N): low = M & (-M) # фиксируем младший элемент — против дублей P = M while P: if (P & low) and subset_sum[P] == 0 and dp[M ^ P] != -1: dp[M] = max(dp[M], dp[M ^ P] + 1) P = (P - 1) & M # перебор подмасок M return m - dp[N - 1]
Сложность — O(3ᵐ) (перебор всех пар «маска, её подмаска»). Звучит пугающе, но для m = 12 это полмиллиона операций — десятки миллисекунд на Python; для m = 15 — пара сотен миллисекунд. А в дружеской компании m обычно ещё меньше, так что ответ появляется мгновенно. Забавный поворот: задача NP-трудная, но в моём случае решается точно и быстро — просто потому, что вход крошечный. Не надо бороться с NP-трудностью, если можно её обойти размером данных.
На том злополучном раскладе +3, +1, −4, +2, −2 эта функция честно возвращает 3, а не 4.
Насколько вообще плоха жадность
Резонный вопрос: а стоило ли городить экспоненту ради экономии одного перевода? Я прогнал обе функции на 4000 случайных раскладов (до 7 человек, балансы в пределах ±5) и сверил с полным перебором разбиений. Точная динамика совпала с брутфорсом везде — приятно, значит формула m − g* и правда работает. А жадный алгоритм оказался строго хуже оптимума примерно в 14 % случаев. Не катастрофа, но и не мелочь: почти каждый седьмой расклад можно было закрыть меньшим числом переводов.
Так что для приложения, где переводы люди делают руками и лишний перевод — это реальное неудобство, точный алгоритм того стоит.
Чем всё кончилось
В ««Сочтёмся»» уехал точный алгоритм: раз m маленькое, платить за оптимальность нечем, а пользователь видит минимально возможное число переводов. Жадный проход остался как ориентир и как быстрый запасной вариант на случай неправдоподобно больших групп.
А мораль вышла двойная. Во-первых, бытовые задачи любят прятать под собой серьёзную теорию — и это кайф, когда наталкиваешься на неё сам, а не в учебнике. А во-вторых, NP-трудность — это приговор алгоритму «в общем случае», а не вашей конкретной задаче: иногда её достаточно просто перерасти размером входных данных.
Пощупать результат живьём можно в боте @WeEvenBot. По коду с удовольствием отвечу в комментариях — там же расскажу, если интересно, как в этом же приложении деньги живут в целых копейках и почему это тоже не мелочь.
ссылка на оригинал статьи https://habr.com/ru/articles/1086822/