算法来确定支付最低还款额之间的一组 [英] algorithm to determine minimum payments amongst a group

问题描述

我最近被要求计算所欠之间的一群人谁在旅途中去一起来到了一个有趣的问题，这些钱：因为你知道，每个人欠另一个金额，什么是一般的算法，以巩固人之间的债务，以便只需要支付的最小数目来进行？拿这个作为一个例子：

I was recently asked to calculate the money owed amongst a group of people who went on a trip together and came upon an interesting problem: given that you know the amounts that each person owes another, what is a general algorithm to consolidate the debts between people so that only the minimum number of payments needs to be made? Take this as an example:

• 在麦克欠约翰·100
• 约翰欠瑞秋200
• 在麦克欠瑞秋400

我们可以通过重订债务像这样删除迈克和约翰之间的付款方式：

We can remove a payment between Mike and John by reformulating the debts like this:

• 在麦克欠约翰0
• 约翰欠瑞秋100
• 在麦克欠瑞秋500

我做数学的手，因为它是很容易，但在我的程序员是渴望找出一个通用算法做了一个任意大集团。这似乎是一个图形算法给我，所以我会改写这是一个图：

I did the math by hand since it was easy enough, but then the programmer in me was itching to figure out a general algorithm to do it for an arbitrarily large group. This seems like a graph algorithm to me, so I'll reformulate this as a graph:

• 的顶点是人组
• 的边执导，所欠金额加权。例如，从麦克瑞秋体重500的边意味着迈克欠瑞秋500。
• 约束：权重为每个节点的净总和必须保持不变
• 目的是找到边缘仍然满足约束的最少数量的曲线图。

推荐答案

这是不够的，只是弄清楚了接收器和度外。虽然我认为这一战略是在正确的轨道，也不能保证一个算法来找出付款尽可能少。

It does not suffice to just figure out the receivers and givers. While I think this strategy is on the right track it also does not ensure an algorithm to find the least possible amount of payments.

例如，

• 在某甲欠25
• 在某乙欠50
• 人物C欠75
• 人·d是欠100
• 在人E被欠50

虽然很明显，这可以在3进行支付（A和C至D，B至E）。我想不出一个高效的算法，将满足这个对所有问题集的。

While it is obvious that this can be done in 3 pays (A and C to D, B to E). I can't think of an efficient algorithm that will satisfy this for all problem sets.

最好的例子，

• 在某甲欠10
• 在某乙欠49
• 人物C欠50
• 人·d欠65
• 在人E被欠75
• 在人F被欠99

如果我们把具有人·d付至F的贪婪的方法，我们会风了一个次优的解决方案，而不是最优（A和D到E，B和C到F）。

If we took the greedy approach of having person D pay to F we would wind up with a sub-optimal solution as opposed to the optimal(A&D to E, B&C to F).

这问题有很多相似性与装箱问题有被证明是NP难。唯一的区别是，我们有不同尺寸的多个二进制元素及条件，在所有仓的总空间是等于所有项目的总大小。这使我相信，问题很可能NP难但有一个额外的限制有可能解决多项式时间。

This problem has a lot of similarity with the Bin Packing Problem which has been proven to be NP-hard. The only difference being that we have multiple bins of varying sizes and the condition that the total space in all bins is equal to the total size of all items. This leads me to believe that the problem is likely NP-hard but with the added constraints it may be possible to solve in polynomially time.

这篇关于算法来确定支付最低还款额之间的一组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！