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

Question

我期待着针对以下问题的算法.

问题:会有一群人欠他们一些钱或没有钱.现在,我需要一个算法(最好和最好的)来解决这个群体中的费用.

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

现在,每人的费用是1500/3 = 500.意思是B给A 100.给B 400.我知道,我可以用最少的金额开始工作.

有人可以指出我最好的一个,如果你有.

提前致谢.

总结一下,1.找出总费用和人均费用.
2.找出欠款或欠款的金额(-ve表示未付款).
3.从最低+ ve量开始.将其分配给-ve金额.
4.继续重复步骤3,直到用完量为止.
秒.转到下一个更大的+ ve号码.继续重复3和4,直到有+ ve数字.

或者有更好的方法吗？我只是好奇.:)

Answer 1

要回零的状态(交易的最低数量),最好的办法是在这个问题涵盖在这里.

Answer 2

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

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

我也不知道您所说的“从花费最少的金额开始并继续前进”是什么意思。

Answer 3

我创建了一个Android应用来解决此问题。您可以在旅途中输入费用，甚至会建议您“下一步谁应该付款”。最后，它计算“谁应该发送多少钱给谁”。我的算法计算出所需的最小交易次数，您可以设置“交易容忍度”，以进一步减少交易次数（您不必担心$ 1交易）。尝试一下，它称为Settle Up：

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

我的算法说明：

我有基本的算法可以解决n-1个事务的问题，但这不是最优的。它的工作方式如下：从付款中，我计算每个成员的余额。余额是他支付的金额减去他应支付的金额。我越来越根据平衡对成员进行排序。然后，我总是拿最穷和最富有的人进行交易。其中至少有一个结余为零，因此不再进行进一步的计算。这样，交易数量不会比n-1差。它还使交易中的金额最小化。但这不是最佳选择，因为它不检测可以在内部建立的子组。

寻找可以在内部安定下来的小组是很难的。我通过生成成员的所有组合并检查子组中的余额总和是否等于零来解决该问题。我从2对开始，然后是3对...（n-1）对。组合生成器的实现可用。当我找到一个子组时，我将使用上述基本算法来计算该子组中的交易。对于每个找到的子组，将保留一笔事务。

该解决方案是最佳的，但是复杂度增加到O（n！）。这看起来很糟糕，但诀窍在于实际上只有少量成员。我已经在Nexus One（1 GHz处理器）上对其进行了测试，结果是：直到10个成员：<100 ms，15个成员：1 s，18个成员：8 s，20个成员：55 s。因此，直到18个成员执行时间都很好。对于15个以上的成员，解决方法是仅使用基本算法（快速且正确，但不是最佳算法）。

源代码：

在有关以捷克语编写的算法的报告中提供了源代码。源代码在结尾，用英语：

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