平衡算法以平衡差异？

Question

假设我们有N个带正余额的账户B_1, ..., B_n。

我们可以进行转账T(from,to,amount)，该操作将在账户之间转移一定金额的余额。

我们已经知道了最优分配余额O_1, ..., O_n。

问题是：如何找到最小的转账集合以实现最优分配？我们是否总能最多只用N-1次转账就完成任务？

示例：

Balances  {0}: 10, {1}: 40, {2}: 50
Optimal   {0}: 20, {1}: 60, {2}: 20

T(2,0,10) => {0}: 20, {1}: 40, {2}: 40
T(2,1,20) => {0}: 20, {1}: 60, {2}: 20

- randomguy

---

是的。因为你永远不会被迫为N个账户进行超过“N-1”次的转账。为什么？必须存在不平衡的情况才需要进行平衡操作。你可以使用线性规划来绘制线性需求。 - Elliott Frisch

随便选一个：https://dev59.com/1nM_5IYBdhLWcg3w8H82 或 https://dev59.com/OG455IYBdhLWcg3wFP9u 或 https://dev59.com/VGUo5IYBdhLWcg3w2CaJ - David Eisenstat

Answer 1

是的，你总是可以通过不超过N-1次转移来解决问题。以下是归纳证明：

1. 对于N=2，很明显只需要一次转移。
2. 对于N>2，有两种情况：
   1. 我们已经处于最优分配状态，此时无需做任何操作。
   2. 存在i和j，使得B_i > O_i且B_j < O_j。将B_i - O_i, O_j - B_j中较小的值从账户i转移到账户j，这样就平衡了这两个账户之一，从而将问题缩小到N-1的规模。

这个证明是具有构造性的，也就提供了一个算法。该算法并不试图将转移次数最小化。

可以很容易地想出启发式算法来减少步骤数。现在已经有点晚了，我不能再花大力气去考虑最优性，但如果这个问题被证明是NP难问题，那也不会让我感到意外。

- NPE

---

对我来说，减少转账数量的问题感觉上等同于找到子集，其中所需的增加和减少总和为0（因为如果你解决了除一个账户之外的所有这些账户，最后一个账户也会自动解决）。然而，子集和是NP完全问题，因此我同意这个问题的最优解似乎很可能是NP难的。 - Peter de Rivaz

@PeterdeRivaz 没错，它是NP难问题。 - David Eisenstat