这是一种更通用的问题，不是语言的。更多的想法和算法的使用。

This is kind of more generic question, isn't language-specific. More about idea and algorithm to use.

的系统，如下：

它注册的朋友群体之间的小额贷款。 爱丽丝和比尔打算吃午饭，比尔的卡不能正常使用，所以爱丽丝支付了他一顿，$ 10 第二天比尔和查尔斯满足对方一个火车站上，Chales没有钱的票，所以比尔给他买一个，$ 5 当天晚些时候，爱丽丝借用$ 5从查尔斯和$ 1从比尔买她的朋友的礼物。

It registers small loans between groups of friends. Alice and Bill are going to lunch, Bill's card isn't working, so Alice pays for his meal, $10. The next day Bill and Charles meet each other on a railway station, Chales has no money for ticket, so Bill buys him one, for $5. Later that day Alice borrows $5 from Charles and $1 from Bill to buy her friend a gift.

现在，假设他们都注册了的交易的系统，它看起来是这样的：

Now, assuming they all registered that transactions in the system, it looks like this:

Alice -> Bill $10
Bill -> Alice $1
Bill -> Charles $5
Charles -> Alice $5

所以，现在，这需要做的唯一一件事就是比尔给爱丽丝 $ 4（他给她$ 1和查理的传输的他的$ 5 爱丽丝 alredy），他们是在初始状态。

So, now, only thing that needs to be done is Bill giving Alice $4 (he gave her $1 and Charlie transferred his $5 to Alice alredy) and they're at the initial state.

如果我们扩展了许多不同势的人，有多个交易，这将是最好的算法来获得尽可能少的交易地？

If we scale that to many diffrent people, having multiple transaction, what would be the best algorithm to get as little transactions as possible?

推荐答案

这其实看起来像一个工作的复式记账的概念可以帮助。

This actually looks like a job that the double entry accounting concept could help with.

您的交易可以被构造为这样会计分录：

Your transactions could be structured as bookkeeping entries thus:

                          Alice  Bill  Charles  Balance
Alice   -> Bill    $10      10    10-       0        0
Bill    -> Alice    $1       9     9-       0        0
Bill    -> Charles  $5       9     4-       5-       0
Charles -> Alice    $5       4     4-       0        0

和你有它。在每一笔交易，你的信用1总​​账账户和借记另一个使天平始终为零。在结尾，您只需计算出的数量降到最低交易被应用到每一个帐户，将其返回到零。

And there you have it. At each transaction, you credit one ledger account and debit another so that the balance is always zero. At at the end, you simply work out the minimal number transactions to be applied to each account to return it to zero.

对于这个简单的情况下，它是从比尔一个简单的$ 4传输给Alice。你需要做的是降低至少一个帐户（但preferably二）加入到零对每一项交易。比方说，你有更复杂的：

For this simple case, it's a simple $4 transfer from Bill to Alice. What you need to do is to reduce at least one account (but preferably two) to zero for every transaction added. Let's say you had the more complicated:

                          Alice  Bill  Charles  Balance
Alice   -> Bill    $10      10    10-       0        0
Bill    -> Alice    $1       9     9-       0        0
Bill    -> Charles  $5       9     4-       5-       0
Charles -> Alice    $5       4     4-       0        0
Charles -> Bill     $1       4     5-       1        0

然后在需要的交易将是：

Then the transactions needed would be:

Bill     -> Alice   $4       0     1-       1        0
Bill     -> Charles $1       0     0        0        0

不幸的是，也有一些州，这种简单的贪心策略不会产生最佳的解决方案（荣誉给 j_random_hacker 指出这一点）。一个例子是：

Unfortunately, there are some states where this simple greedy strategy does not generate the best solution (kudos to j_random_hacker for pointing this out). One example is:

                 Alan  Bill  Chas  Doug  Edie  Fred  Bal
Bill->Alan   $5    5-    5     0     0     0     0    0
Bill->Chas  $20    5-   25    20-    0     0     0    0
Doug->Edie   $2    5-   25    20-    2     2-    0    0
Doug->Fred   $1    5-   25    20-    3     2-    1-   0

显然，这可以在四个招式逆转（因为4的动作，是所有花到那里），但是，如果你选择你的第一个举动不明智（Edie-＆G​​T;比尔$ 2），五是最小的，你会逃脱。

Clearly, this could be reversed in four moves (since four moves is all it took to get there) but, if you choose your first move unwisely (Edie->Bill $2), five is the minimum you'll get away with.

您可以解决这个问题的尤其的问题与以下规则：

You can solve this particular problem with the following rules:

（1）如果你可以消灭两个余额，做到这一点。 （2），否则的话，你可以消灭一平，并设置自己擦了两次，在下一步的行动，做到这一点。 （3）否则，消灭任何一个平衡点。

这将导致如下序列：

（一）[1]不适用，[2]可以实现 Alan-＆GT;比尔$ 5 （二）[1]可以用做 Chas-＆GT;比尔$ 20个 （c）和（d）中，类似的推理道格，伊迪和弗雷德，四个总举动。 (a) [1] not applicable, [2] can be achieved with Alan->Bill $5. (b) [1] can be done with Chas->Bill $20. (c) and (d), similar reasoning with Doug, Edie and Fred, for four total moves.

不过，这工作，因为少数的可能性根本。随着人口数量上升，该集团相互关系变得更加复杂，你很可能需要一个详尽的搜索找到所需的移动最小数量（1，2和3以上的基本规则，但扩展到处理更多的深度）

However, that works simply because of the small number of possibilities. As the number of people rises and the group inter-relations becomes more complex, you'll most likely need an exhaustive search to find the minimum number of moves required (basically the rules 1, 2 and 3 above but expanded to handle more depth).

我认为这是什么将被要求提供您的最小交易数量在所有情况下。然而，它可以是这不是必需的的最好的答案（最好，在这种情况下，这意味着最大每个降压砰）。这可能是因为连基本的1/2/3规则集会给您目的的足够好的答案。

I think that is what will be required to give you the smallest number of transactions in all circumstances. However, it may be that that's not required for the best answer (best, in this case, meaning maximum "bang per buck"). It may be that even the basic 1/2/3 rule set will give you a good-enough answer for your purposes.