在组之间分摊/结算费用的算法

Question

我期待着一个算法来解决以下问题。

问题:将会有一群人彼此欠钱或什么都不欠。现在，我需要一个算法(最好的和整洁的)来结算这组人的费用。

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

现在，人均费用是1500/3 = 500。意思是B给A 100分。B给C 400。我知道，我可以从花费最少的钱开始，然后继续工作。

如果你有，谁能给我点个最好的。

提前谢谢。

总而言之，1.找出总费用和人均费用。

1. 找出每个欠款或未付的金额(-ve表示具有最小+ve金额的outstanding).
2. Start。将其分配至-ve金额。
3. 将继续重复步骤3，直到用完-ve金额。

移动到下一个更大的+ve数字。继续重复3&4，直到有+ve数字。

或者还有更好的办法吗？我只是好奇。:)

Answer 1

你已经描述过了。将所有费用相加(在您的情况下为1500)，除以分担费用的人数(500)。对于每个人，从个人份额中扣除该人的贡献(对于个人A，从500中减去400 )。结果是个人“欠”中央池的净值。如果任何人的数字为负数，则中央池将“欠”该人。

因为您已经描述了解决方案，所以我不知道您在问什么。也许你试图在没有中央池的情况下解决这个问题，“银行”？

我也不知道你说的“从花费最少的钱开始，然后继续工作”是什么意思。

Answer 2

在本问题here中介绍了恢复到零状态(最小事务数)的最佳方法。

Answer 3

我已经创建了一个Android应用程序来解决这个问题。你可以在旅途中输入费用，它甚至会建议你“谁应该支付下一个费用”。最后，它会计算“谁应该发送多少给谁”。我的算法计算出所需的最小交易数量，你可以设置“交易容差”，它可以进一步减少交易(你不关心1美元的交易)，尝试一下，它被称为setup：

https://market.android.com/details?id=cz.destil.settleup

我的算法：的描述

我有解决n-1个事务的问题的基本算法，但它不是最优的。它的工作原理是这样的:从付款中，我计算每个成员的余额。余额是他支付的金额减去他应该支付的金额。我越来越多地按照平衡对成员进行排序。然后，我总是选择最贫穷和最富有的人，然后进行交易。它们中至少有一个最终为零余额，并被排除在进一步的计算之外。这样，事务的数量不能低于n-1。它还可以最大限度地减少交易中的金额。但它并不是最优的，因为它不会检测到可以在内部解决的子组。

很难找到可以在内部解决的子组。我通过生成成员的所有组合并检查子组中的余额和是否等于零来解决它。我从2对开始，然后是3对...(n-1)对。组合生成器的实现是可用的。当我找到一个子组时，我会使用上面描述的基本算法来计算子组中的事务。对于每个找到的子组，将保留一个事务。

解决方案是最优的，但复杂度增加到O(n!)。这看起来很可怕，但诀窍是实际上只有少量的成员。我已经在Nexus One (1 Ghz处理器)上测试了它，结果是:直到10个成员：<100ms，15个成员:1 s，18个成员:8 s，20个成员: 55 s，所以直到18个成员执行时间是很好的。对于大于15的成员，解决方法是只使用基本算法(它既快速又正确，但不是最优的)。

源码：

源代码可以在捷克语写的关于算法的报告中找到。源代码在最后，是英文的：

http://www.settleup.info/files/master-thesis-david-vavra.pdf