分账算法如何最小化转账次数
记录完花费后,分账计算器会把一张错综复杂的「谁欠谁」关系图,化简成最少次数的转账。这项技术称为「债务简化(Debt Simplification)」。
1. 算出每个人的净余额
针对每个人,把「他付出的总额」减去「他应分摊的总额」。结果为正数代表别人要还他钱,负数代表他要付钱给别人。
2. 把最大的债务人配对最大的债权人
把欠最多的人,与被欠最多的人配成一组,一次转账尽可能同时抵消双方余额。
3. 重复直到所有人归零
每配对一次,金额较小的一方余额就被抵消并移除,接着处理下一组。这个贪心算法能保证用最少的转账次数结清。