分帳演算法如何最小化轉帳次數
記錄完花費後,分帳計算機會把一張錯綜複雜的「誰欠誰」關係圖,化簡成最少次數的轉帳。這項技術稱為「債務簡化(Debt Simplification)」。
1. 算出每個人的淨餘額
針對每個人,把「他付出的總額」減去「他應分攤的總額」。結果為正數代表別人要還他錢,負數代表他要付錢給別人。
2. 把最大的債務人配對最大的債權人
把欠最多的人,與被欠最多的人配成一組,一次轉帳盡可能同時抵銷雙方餘額。
3. 重複直到所有人歸零
每配對一次,金額較小的一方餘額就被抵銷並移除,接著處理下一組。這個貪婪演算法能保證用最少的轉帳次數結清。