用于确定组中最小支付的算法

Question

问题

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

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

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

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

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

以图表形式查看

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

Answer 1

我的意见是:你让这个过于复杂.

把它看成是钱的"池",完全失去了关系:

代替:

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

算法只需要思考:

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

净化这个:

• 迈克欠500
• 约翰欠100
• 雷切尔欠600

将其分为"给予者"和"接收者"列表.列表中的每个给予者将通过接收者列表,为每个接收者提供他们需要的东西,直到给予者为止.当接收器收到他们需要的所有东西时,他们就会从列表中删除.

稍后编辑

正如其他海报所观察到的那样,这简化了问题.但是,"给予者"和"接收者"列表可能存在最佳排序,但我们尚未找到确定此排序的直接方法.

Answer 2

仅仅弄清楚接收器和提供者是不够的.虽然我认为这种策略是在正确的轨道上,但它也无法确保算法找到尽可能少的支付金额.

例如,

• A人欠25
• B人欠50
• 人C欠75
• 人D欠100
• 人E欠50

虽然很明显这可以用3个支付(A和C到D,B到E)来完成.我想不出一个能满足所有问题集的高效算法.

更好的例子,

• 人A欠10
• B人欠49
• 人C欠50
• 人D欠65
• 人E欠75
• 人F欠99

如果我们采用贪婪的方法将人D付给F,我们最终会得到次优解,而不是最优解(A&D到E,B&C到F).

这个问题与Bin Packing问题有很多相似之处,而Bin Packing问题已被证明是NP难的.唯一的区别是我们有多个不同大小的箱子以及所有箱子中的总空间等于所有物品的总大小的条件.这让我相信这个问题很可能是NP难的,但是在增加的约束条件下,它可能在多项式时间内得到解决.

Answer 3

虽然我同意@Andrew 的观点，认为将其转化为图形问题可能过于复杂，但我不确定他的方法会产生最少的交易数量。这就是你在现实生活中解决问题的方法，以免让自己头疼。只是集中钱。

一些看似“正确”的步骤：

• 清除所有零债务个人；他们不需要向任何人汇款或收款。
• 将所有给予者和接受者配对，并具有相同的欠款/欠款金​​额。由于非零债务的每个节点的最小连接度为 1，因此如果它们只是互相支付，那么它们的交易量就已经是最小的了。从图表中删除它们。
• 从需要偿还金额最大的个人开始，创建一个包含欠款金额低于该金额的所有接收者的列表。尝试所有支付组合，直到找到一种可以让大多数接收者通过一笔交易满意的支付组合。“节省”剩余的剩余债务。
• 继续寻找下一个最大的捐赠者，等等。
• 将所有剩余债务分配给剩余的接收者。

与往常一样，恐怕我对前两个步骤相当确定，但对其他步骤不太确定。无论如何，这听起来确实像是教科书上的问题。我确信那里有一个“正确”的答案。

Answer 4

看看这篇博客文章" 最佳帐户平衡 ",完全解决您的问题.

Answer 5

在企业财务领域，这被称为支付或结算净额结算。

跨国公司通常每个月在其子公司之间有大量的资金流动，而且通常以不同的货币进行。通过优化这些流量的结算，他们可以节省大量资金。通常，公司每月执行一次此类优化（净额结算周期）。当存在多种货币时，储蓄来源有以下三种：

• 银行交易费用（付款越少意味着费用越低）
• 银行简化处理流程，降低利率浮动和结算风险（资金在银行系统中占用的时间更少）
• 外汇匹配（兑换的外币要少得多，因为大部分都被“扣除”）

有两种方法可以实际计算优化沉降。

双边净额结算是 @AndrewShepherd 在本页上详细描述的解决方案。然而，在跨境实施中，这种方法可能会产生法律和行政问题，因为每个月都会跨越不同的边界。

多边净额结算通过添加一个称为净额结算中心的新子公司来解决网络问题，并通过它重新路由所有金额。比较之前和之后的图如下：

结网前

结网后

虽然这增加了不必要的流量（与双边净额结算相比），但优点是：

• 计算更简单，结果更容易可视化（而且，只有一种解决方案，而不是双边方法）
• 净额结算中心成为整个集团内有关流量和外汇敞口的宝贵资源
• 例如，如果净额结算中心位于德国，那么所有跨境支付的法律问题都将在净额结算中心所在国一劳永逸地得到解决（中央银行报告等）
• 优化结算所需的所有外汇均可从净额结算中心买卖

（在基本层面上，计算很简单，但可能存在许多法律和行政复杂性，因此企业经常从软件供应商或服务提供商处开发或购买净额结算系统。）