Итак, я реализовал это для электронной таблицы, чтобы отслеживать долги моих соседей по комнате друг перед другом. Я знаю, что это действительно старая версия, но я сослался на нее в своем решении, и она высоко ценится в Google при поиске этой темы, поэтому я хотел опубликовать и посмотреть, есть ли у кого-нибудь какие-либо комментарии.
Мое решение использует концепцию "центральный банк" или "центр неттинга", упомянутую здесь. Перед запуском этого алгоритма я рассчитываю чистую прибыль, причитающуюся каждому человеку, которая представляет собой сумму всех их кредитов за вычетом суммы всех их долгов. Сложность расчета этого зависит от количества транзакций, а не от числа вовлеченных лиц.
По сути, суть алгоритма заключается в том, чтобы каждому человеку платили или выплачивали правильную сумму независимо от того, кому он переводит деньги. В идеале я хотел бы сделать это за наименьшее количество платежей, однако доказать это трудно. Обратите внимание, что все дебеты и кредиты будут равны нулю.
Я был очень, очень многословен для части этого кода. Частично, чтобы сообщить, что я делал, и частично, чтобы укрепить логику, которую я использую, когда я иду вперед. Извиняюсь, если это не читается.
Input: {(Person, Net Profit)} //Net Profit < 0 is debt, Net Profit > 0 is credit.
Output: {(Payer, Payee, Amount paid)}
find_payments(input_list):
if input_list.length() > 2:
//More than two people to resolve payments between, the non-trivial case
max_change = input_list[0]
not_max_change = []
//Find person who has the highest change to their account, and
//the list of all others involved who are not that person
for tuple in input_list:
if abs(tuple[Net Profit]) > abs(max_change[Net Profit])
not_max_change.push(max_change)
max_change = tuple
else:
not_max_change.push(tuple)
//If the highest change person is owed money, they are paid by the
//person who owes the most money, and the money they are paid is deducted
//from the money they are still owed.
//If the highest change person owes money, they pay the person who
//is owed the most money, and the money they pay is deducted
//from the money they are still owe.
not_yet_resolved = []
if max_change[Net Profit] > 0:
//The person with the highest change is OWED money
max_owing = not_max_change[0]
//Find the remaining person who OWES the most money
//Find the remaining person who has the LOWEST Net Profit
for tuple in not_max_change:
if tuple[Net Paid] < max_owing[Net Paid]:
not_yet_resolved.push(max_owing)
max_owing = tuple
else:
not_yet_resolved.push(tuple)
//The person who has the max change which is positive is paid
//by the person who owes the most, reducing the amount of money
//they are owed. Note max_owing[Net Profit] < 0.
max_change = [max_change[Person], max_change[Net Profit]+max_owing[Net Profit]]
//Max_owing[Person] has paid max_owing[Net Profit] to max_change[Person]
//max_owing = [max_owing[Person], max_owing[Net Profit]-max_owing[Net Profit]]
//max_owing = [max_owing[Person], 0]
//This person is fully paid up.
if max_change[Net Profit] != 0:
not_yet_resolved.push(max_owing)
//We have eliminated at least 1 involved individual (max_owing[Person])
//because they have paid all they owe. This truth shows us
//the recursion will eventually end.
return [[max_owing[Person], max_change[Person], max_owing[Net Profit]]].concat(find_payments(not_yet_resolved))
if max_change[Net Profit] < 0:
//The person with the highest change OWES money
//I'll be way less verbose here
max_owed = not_max_change[0]
//Find who is owed the most money
for tuple in not_max_change:
if tuple[Net Paid] > max_owed[Net Paid]:
not_yet_resolved.push(max_owed)
max_owed = tuple
else:
not_yet_resolved.push(tuple)
//max_change pays the person who is owed the most.
max_change = [max_change[Person], max_change[Net Profit]+max_owed[Net Profit]]
if max_change[Net Profit] != 0:
not_yet_resolved.push(max_owing)
//Note position of max_change[Person] moved from payee to payer
return [[max_change[Person], max_owed[Person], max_owed[Net Profit]]].concat(find_payments(not_yet_resolved))
//Recursive base case
//Two people owe each other some money, the person who owes pays
//the person who is owed. Trivial.
if input_list.length() == 2:
if input_list[0][Net Profit] > input_list[1][Net Profit]:
return [[input_list[1][Person], input_list[0][Person], input_list[0][Net Profit]]];
else
return [[input_list[0][Person], input_list[1][Person], input_list[1][Net Profit]]];
Примечание:
max_change = (payee, $A); max_owing = (payer, $B)
|$A|>=|$B| by nature of 'max_change'
$A > 0 => $A >= |$B| //max_change is owed money
$B < 0 by nature of 'max_owing'
$A >= -$B => $A + $B >= 0 => Payee does not go into debt
и
max_change = (payee, $A); max_owed = (payer, $B)
|$A|>=|$B| by nature of 'max_change'
$A < 0 => -$A >= |$B| //max_change owes money
$B > 0 by nature of 'max_owed'
-$A >= $B => 0 >= $A + $B => Payee does not go into credit
также:
Sum of Payments = 0 = $A + $B + Remainder = ($A + $B) + 0 + Remainder
Сумма, всегда равная 0 после полного погашения чьего-либо долга, является основой логики рекурсии. Кто-то заплатил / заплатил, проблема становится меньше.
Если этот алгоритм работает для n людей с ненулевыми долгами (откажитесь от людей, которые обанкротились еще до запуска алгоритма), этот алгоритм даст не более n-1 платежей для погашения задолженности. Неясно, всегда ли это идеальная схема оплаты (я пока не нашел встречного примера). Я могу попытаться доказать, что если количество транзакций
Я чрезвычайно заинтересован в любых ошибках, которые кто-либо видит в этом. Я давно не занимался разработкой, не говоря уже о алгоритмах, и люди будут платить друг другу за это. Мне было весело, и это интересный, мясистый вопрос, надеюсь, некоторые из вас все еще рядом.