在一组之间共享/结算费用的算法

Question

我期待着解决以下问题的算法。

问题:会有一组人互相欠钱或不欠钱。现在，我需要一种算法(最好的和简洁的)来解决这个群体的费用。

Person AmtSpent
------ ---------
A       400  
B      1000  
C       100  
Total  1500

现在，每人的支出是 1500/3 = 500。意思是 B 给 A 100。B 给 C 400。我知道，我可以从最少的支出开始，然后再往前推进。

谁能告诉我最好的一个，如果有的话。

总结一下，

1. 找出总费用和人均费用。
2. 找出每个欠款或未付金额(-ve 表示未付金额)。
3. 从最少的 +ve 量开始。分配给 -ve 数量。
4. 不断重复第 3 步，直到用完 -ve 数量。
   秒。移动到下一个更大的 +ve 数字。不断重复 3 和 4，直到有 +ve 个数字。

或者有什么更好的办法吗？

Answer 1

返回零状态(最小事务数)的最佳方法已在这个问题中介绍 here .