这是一种更通用的问题,不是特定于语言的.更多关于使用的想法和算法.

系统如下:

它在朋友群之间登记小额贷款.Alice并且Bill要去吃午饭,比尔的卡不工作,所以爱丽丝支付他的餐费,10美元.
第二天Bill,Charles在火车站相遇,Chales没有钱买票,所以Bill买了一个,5美元.那天晚些时候从她和朋友那里Alice借了5美元Charles和1美元Bill购买礼物.

现在,假设他们都在系统中注册了这些事务,它看起来像这样:

Alice -> Bill $10
Bill -> Alice $1
Bill -> Charles $5
Charles -> Alice $5

所以,现在,唯一需要做的就是Bill给Alice4美元(他给了她1美元并将他的5 美元Charlie 转移到Alicealredy)并且他们处于初始状态.

如果我们将这个扩展到许多不同的人,拥有多个事务,那么获得尽可能少的事务的最佳算法是什么？

问题

我最近被要求计算一起去旅行的一群人所欠的钱,并且遇到了一个有趣的问题:假设你知道每个人欠另一个人的金额,那么巩固人与人之间债务的一般算法是什么？这样只需要支付最少的款项？以此为例:

• 迈克欠约翰100
• 约翰欠雷切尔200
• 迈克欠雷切尔400

我们可以通过重新制定这样的债务来取消迈克和约翰之间的付款:

• 迈克欠约翰0
• 约翰欠Rachel 100
• 迈克欠雷切尔500

我手工完成了数学计算,因为它很容易,但是后来我的程序员很想找到一个通用的算法来为一个任意大的组做这个.这对我来说似乎是一个图算法,所以我将其重新表示为图:

以图表形式查看

• 顶点是组中的人
• 边缘由所欠的金额定向和加权.例如,从Mike到Rachel的重量为500的边缘意味着Mike欠Rachel 500.
• 约束:每个节点的净重和必须保持不变.
• 目标是找到具有仍满足约束的最小边数的图.

上下文

我正在创建一个程序来简化人与人之间的共享费用.费用有:

• 最初支付费用的付款人
• 一些贡献者,他们将支付一部分费用(注意付款人也是贡献者)

捐助者必须为某项费用支付的股份不一定必须相等.经过一些任意数量的开支后,有些人会欠钱,而其他人欠钱.

问题

问题是找到一个让所有人解决债务的简单方法.我想要一个人最多支付另一个人的费用,而不是某些人不得不支付其他几个人,而有些人根本不需要支付任何费用.此外,我想尽量减少一个人收到的超出他或她实际欠款的金额.例如,如果你欠100美元,你真的不想收到2000美元,并且必须向其他人转发1900美元.

模型

每个人都有债务.债务是:

• 如果这个人欠钱就是积极的
• 如果该人欠款,则为负数
• 零,如果以上都不是

因此,该模型由一组数字组成,代表债务.

这是一个零和的情况:人们所欠的钱数等于人们所欠的钱数(没有贷款人就没有贷款).这意味着无论谁收到付款,如果最后每个人都支付了欠款,就没有人欠任何钱.

安妮支付鲍勃100美元.如果安妮有100的债务,她的债务现在为0.如果鲍勃的债务为-100,他的债务也是0.在该模型中,货币交易相当于从付款人的债务中扣除,并添加相同的债务相当于收件人的.

为了最大限度地减少交易中收款人的超额收款,我认为将最大的正债务加到每笔交易的最大负债中应该足够了.

履行

我正在考虑为负债使用最小堆,为正债使用最大堆.然后重复执行从最大最大到最小最小的事务.这可以通过将min的键增加最大值并删除max来完成.如果债务为零,则将其从堆中删除.

伪代码

让我们max成为最大元素maxHeap和min最小元素minHeap.max.person和min.person是谁持有的债务的人max,并min分别.

while(not done) do:
    new transaction.from(max.person).to(min.person)
    if(max + min = 0) then:               //remove both
        maxHeap.removeMax
        minHeap.removeMin
    else if (max + min < 0) then:         //keep in minHeap
        minHeap.increaseKey(min).by(max)
        maxHeap.removeMax
    else                                  //move min to maxHeap
        maxHeap.decreaseKey(max).by(|min|)

如果我没弄错的话,这应该给我O(nlogn)的运行时间.

题

我的推理是否正确？根据我的问题描述,我的解决方案会得到相当好的结果吗？有没有其他人有更快和/或更简单的解决方案,仍然坚持尽可能少收到多余资金的标准？

注意:如果它重要,我将用Java实现它

编辑:我发现了另一个与此类似的问题:在一个组中分享/结算费用的算法.但是,它并没有解决我的问题,因为我有每个人最多一笔交易的标准.