人与人之间转移账户平衡的最优方式

Question

我正在寻找一个最佳的方式转移资金之间的帐户，以确保每个人都有相同的金额在他们的帐户。我正确地计算了每个帐户中的数字，这应该是一个结果，但我正在寻找一个算法，以确定谁应该转帐，以及有多少资金(没有中央银行)，所以每个人都有相同的余额。

示例

+--------+---------+
| person | balance |
+--------+---------+
| A      | 7 500   |
| B      | -2 500  |
| C      | -10 000 |
| D      | 15 000  |
+--------+---------+

在这个例子中，每个人最终都应该得到2500的余额。为实现这一目标：

• 个人A应将5 000人转至B人
• 人D应将12 500人转至C

人

综上所述，我拥有的数据如下：

• 人数(>= 2)
• 开始平衡每个人的
• 每个人在转移

之后应该有什么平衡

有什么算法吗？这是NP完全问题吗？

Answer 1

这个问题很难解决.它本质上等同于this other problem

给出了一组人和一定数量的贷方和借方，找出了这些人之间的最低转账次数来结清所有的贷方和借方。

在这里，你的目标是使每个人的总数与平均值相等，这基本上和上面的问题相同，如果你从每个人的账户中减去平均值的话。