债务优化算法

Question

你可能会提出什么算法来解决下一个任务？或者其他已知的优化任务类似于它？

你有N个人(N > 2)。有些人欠别人钱。你需要优化他们之间的资金流。

示例：

• P1欠P2 30美元
• P1欠P3 10美元
• P2欠P3 20美元

优化将是：

• P1欠P2 10美元
• P1欠P3 30美元

Answer 1

我想我找到了一个很好的解决办法。

1. 计算每个人的最终状态(图中的节点)。您可以通过将所有收入值之和给这个人/节点并减去所有的结果来做到这一点。在我的例子中： 地位：

- P1: -40 USD
- P2: 10 USD
- P3: 30 USD

​

1. 把最小的数字(总是负的)和最大的数字(总是正数)匹配起来，并更新最终雕像的列表。例如： 匹配：

- P1 owes P3: 30 USD.

地位：

- P1: -10 USD
- P2: 10 USD

​

1. 重复2，直到所有匹配(状态列表为空)。 匹配：

- P1 owes P3: 30 USD
- P1 owes P2: 10 USD

​

Answer 2

如果您仍然在寻找解决方案，这里是来自其他StackOverflow问题的答案，它深入到所有解决方案的可能性中。链接：Algorithm to simplify a weighted directed graph of debts

第一个答案给出了算法的一些想法。但是第二个答案与关于这个问题的深入的学术论文有联系。