语境
我正在创建一个程序来简化人与人之间的费用共享。费用有:
出资人必须支付的一定份额的份额不必一定相等。在任意支出一些费用之后，某些人将被欠款，而其他人将被欠款。
问题
问题是为所有人民找到一种轻松的方式来偿还债务。我希望有些人不必多付其他人，而有些人根本不用付任何人的钱，我希望一个人最多只能付给另一个人。此外，我想使一个人获得的超出他或她实际欠款的多余钱减少到最低限度。例如，如果您被欠100美元，您实际上就不想收到2000美元，而必须将1900美元转给其他人。
模型
每个人都有债务。债务是:
因此，该模型由代表债务的一组数字组成。
这是零和的情况:人们所欠的钱等于人们所欠的钱(没有放贷人就不可能有贷款)。这意味着，无论谁收到付款，如果最后每个人都已经偿还了欠款，就不会有人被欠任何钱。
安妮付给鲍勃100美元。如果Anne的债务为100，则她的债务现在为0。如果Bob的债务为-100，则他的债务也为0。在模型中，货币交易等于从付款人的债务中减去，再加上相同的值等于接收者的。
为了最大程度地减少交易中收款人收到的多余资金，我认为对于每笔交易，将最大的正债务与最大的负债务相加就足够了。
执行
我正在考虑对负债务使用最小堆，对正债务使用最大堆。然后重复执行从最大最大到最小最小的事务。这可以通过将min的键值增加max的值，然后删除max来完成。如果债务为零，请从堆中将其删除。
伪码
令
max为maxHeap的最大元素，而min为minHeap的最小元素。 max.person和min.person是分别持有max和min债务的人。while(not done) do:
new transaction.from(max.person).to(min.person)
if(max + min = 0) then: //remove both
maxHeap.removeMax
minHeap.removeMin
else if (max + min < 0) then: //keep in minHeap
minHeap.increaseKey(min).by(max)
maxHeap.removeMax
else //move min to maxHeap
maxHeap.decreaseKey(max).by(|min|)
如果我没有记错的话，这应该给我一个O(nlogn)的运行时间。
问题
我的推理正确吗？根据我的问题描述，我的解决方案能否给出很好的结果？还有其他人有更快和/或更简单的解决方案，仍然坚持尽可能少收到多余资金的标准吗？
注意:如果有任何关系，我将用Java实现
编辑:我发现了另一个与此非常相似的问题:Algorithm to share/settle expenses among a group。但是，这并不能解决我的问题，因为我的标准是每个人最多可以进行一次交易。
最佳答案
我已经编辑了答案，也可以解决一个接收者可能从多人接收钱而不仅仅是从一个人接收钱的情况。看到最下面。
有趣的问题-必须对其进行编码。此处的伪数据和数据，如Dyalog APL所做的那样。
通常，确保最佳状态的唯一方法是使用蛮力。对于您的问题，当参与者人数大约为12个或更少时，此方法效果很好:
┌──┬──┬──┬──┬───┬───┬─────┬──────┬───────┬─────────┬──────────┬───────────┬─────────────┬──────────────┬─────────────────┐
│!1│!2│!3│!4│!5 │!6 │!7 │!8 │!9 │!10 │!11 │!12 │!13 │!14 │!15 │
├──┼──┼──┼──┼───┼───┼─────┼──────┼───────┼─────────┼──────────┼───────────┼─────────────┼──────────────┼─────────────────┤
│1 │2 │6 │24│120│720│5,040│40,320│362,880│3,628,800│39,916,800│479,001,600│6,227,020,800│87,178,291,200│1,307,674,368,000│
└──┴──┴──┴──┴───┴───┴─────┴──────┴───────┴─────────┴──────────┴───────────┴─────────────┴──────────────┴─────────────────┘
如我们所见，数字阶乘迅速增加。如果有10个参与者，这仍然是一个合理的360万人，那么12个人已经是1/2亿。可能不值得考虑更多。
但是，如果我们谈论的是足够小的帮派，那么进行计算(除了一件事情之外)是微不足道的。
您已设置此条件:
那并不会改变计算本身，但是我不在这个答案之外份额如何得出。您必须有一种方法来确定什么属于谁。此处计算的必要条件是和之和应支付的金额与所支付的金额等于。
考虑以下示例:
我们有4个人消费了400美元。一个人付了全部钱，他们决定平均分担费用:
┌──────────┬───┬───┬───┬───┬─────┐
│Guy │1 │2 │3 │4 │Total│
├──────────┼───┼───┼───┼───┼─────┤
│Should pay│100│100│100│100│400 │
├──────────┼───┼───┼───┼───┼─────┤
│Payed │0 │0 │0 │400│400 │
└──────────┴───┴───┴───┴───┴─────┘
由于第1个人支付了0，因此他显然需要额外支付100，以此类推。这是一个简单的情况。唯一的解决方案是:
1 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬──────┬──────┬──────┬──────┬─────┬────────┐
│Guy # │1 │2 │3 │4 │Total│Turnover│
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Should pay │100 │100 │100 │100 │400 │ │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Has paid │0 │0 │0 │400 │400 │ │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Gets from the one to left│0.00 │100.00│200.00│300.00│ │600 │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Pays to the one to right │100.00│200.00│300.00│0.00 │ │600 │
└─────────────────────────┴──────┴──────┴──────┴──────┴─────┴────────┘
请注意，表格会自动换行-最左边和最右边是“邻居”。
我们看到几乎每个人都向表中的右邻居列付款，并且类似地从他的左邻居列中付款。当加上他最初支付的金额，现在所获得的金额以及现在所支付的金额时，他最终得到分配给他的正确的总费用。
但是，如果＃2支付了100，而＃4支付了300:
┌──────────┬───┬───┬───┬───┬─────┐
│Guy │1 │2 │3 │4 │Total│
├──────────┼───┼───┼───┼───┼─────┤
│Should pay│100│100│100│100│400 │
├──────────┼───┼───┼───┼───┼─────┤
│Payed │0 │100│0 │300│400 │
└──────────┴───┴───┴───┴───┴─────┘
我们得到3种解决方案，其中最好的一种:
3 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬──────┬──────┬──────┬────┬─────┬────────┐
│Guy # │1 │3 │4 │2 │Total│Turnover│
├─────────────────────────┼──────┼──────┼──────┼────┼─────┼────────┤
│Should pay │100 │100 │100 │100 │400 │ │
├─────────────────────────┼──────┼──────┼──────┼────┼─────┼────────┤
│Has paid │0 │0 │300 │100 │400 │ │
├─────────────────────────┼──────┼──────┼──────┼────┼─────┼────────┤
│Gets from the one to left│0.00 │100.00│200.00│0.00│ │300 │
├─────────────────────────┼──────┼──────┼──────┼────┼─────┼────────┤
│Pays to the one to right │100.00│200.00│0.00 │0.00│ │300 │
└─────────────────────────┴──────┴──────┴──────┴────┴─────┴────────┘
最糟糕的是:
Worst solution:
┌─────────────────────────┬──────┬──────┬──────┬──────┬─────┬────────┐
│Guy # │1 │2 │4 │3 │Total│Turnover│
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Should pay │100 │100 │100 │100 │400 │ │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Has paid │0 │100 │300 │0 │400 │ │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Gets from the one to left│100.00│200.00│200.00│0.00 │ │500 │
├─────────────────────────┼──────┼──────┼──────┼──────┼─────┼────────┤
│Pays to the one to right │200.00│200.00│0.00 │100.00│ │500 │
└─────────────────────────┴──────┴──────┴──────┴──────┴─────┴────────┘
上述情况更糟，因为结算付款时的总营业额更大。您具有以下条件:
在大多数情况下这似乎是可能的，但我怀疑是否有任何保证。
现在考虑这种情况:
┌──────────┬──┬──┬──┬──┬──┬──┬──┬──┬─────┐
│Guy │1 │2 │3 │4 │5 │6 │7 │8 │Total│
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Should pay│10│10│10│10│10│10│10│10│80 │
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Payed │0 │0 │0 │0 │0 │0 │0 │80│80 │
└──────────┴──┴──┴──┴──┴──┴──┴──┴──┴─────┘
最佳(也是唯一)解决方案是:
1 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬────────┐
│Guy # │1 │2 │3 │4 │5 │6 │7 │8 │Total│Turnover│
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼────────┤
│Should pay │10 │10 │10 │10 │10 │10 │10 │10 │80 │ │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼────────┤
│Has paid │0 │0 │0 │0 │0 │0 │0 │80 │80 │ │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼────────┤
│Gets from the one to left│0.00 │10.00│20.00│30.00│40.00│50.00│60.00│70.00│ │280 │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼────────┤
│Pays to the one to right │10.00│20.00│30.00│40.00│50.00│60.00│70.00│0.00 │ │280 │
└─────────────────────────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴────────┘
我们看到付款金额增加了。即使＃7的债务只有10，他也得到60并支付70。原因是所有其他人必须积累/积累的额度足以支付给＃8。因为标准是＃8(以及每个人也只能)从另一个人那里得到钱，而不是多个人。
现在考虑一个更复杂的菜单-每个菜单都有自己的选择。有些人为自己的食物付费，而＃8负责支付＃1，＃3，＃5，＃7和他自己的费用:
┌──────────┬──┬──┬──┬──┬──┬──┬──┬──┬─────┐
│Guy │1 │2 │3 │4 │5 │6 │7 │8 │Total│
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Should pay│10│25│12│18│16│10│18│15│124 │
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Payed │0 │25│0 │18│0 │10│0 │71│124 │
└──────────┴──┴──┴──┴──┴──┴──┴──┴──┴─────┘
结果是相当不错的。那些为自己买单的人不受影响:
97 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬─────┬─────┬─────┬─────┬─────┬────┬────┬────┬─────┬────────┐
│Guy # │1 │3 │5 │7 │8 │2 │4 │6 │Total│Turnover│
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Should pay │10 │12 │16 │18 │15 │25 │18 │10 │124 │ │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Has paid │0 │0 │0 │0 │71 │25 │18 │10 │124 │ │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Gets from the one to left│0.00 │10.00│22.00│38.00│56.00│0.00│0.00│0.00│ │126 │
├─────────────────────────┼─────┼─────┼─────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Pays to the one to right │10.00│22.00│38.00│56.00│0.00 │0.00│0.00│0.00│ │126 │
└─────────────────────────┴─────┴─────┴─────┴─────┴─────┴────┴────┴────┴─────┴────────┘
然后是一种情况，显然好汉们掏空了所有口袋并得到了124美元的报酬:
┌──────────┬──┬──┬──┬──┬──┬──┬──┬──┬─────┐
│Guy │1 │2 │3 │4 │5 │6 │7 │8 │Total│
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Should pay│10│25│12│18│16│10│18│15│124 │
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Payed │17│20│10│19│10│20│16│12│124 │
└──────────┴──┴──┴──┴──┴──┴──┴──┴──┴─────┘
非常好!没有大笔钱可动:
67 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬────┬────┬────┬────┬─────┬─────┬────┬────┬─────┬────────┐
│Guy # │1 │3 │4 │8 │5 │6 │7 │2 │Total│Turnover│
├─────────────────────────┼────┼────┼────┼────┼─────┼─────┼────┼────┼─────┼────────┤
│Should pay │10 │12 │18 │15 │16 │10 │18 │25 │124 │ │
├─────────────────────────┼────┼────┼────┼────┼─────┼─────┼────┼────┼─────┼────────┤
│Has paid │17 │10 │19 │12 │10 │20 │16 │20 │124 │ │
├─────────────────────────┼────┼────┼────┼────┼─────┼─────┼────┼────┼─────┼────────┤
│Gets from the one to left│7.00│0.00│2.00│1.00│4.00 │10.00│0.00│2.00│ │26 │
├─────────────────────────┼────┼────┼────┼────┼─────┼─────┼────┼────┼─────┼────────┤
│Pays to the one to right │0.00│2.00│1.00│4.00│10.00│0.00 │2.00│7.00│ │26 │
└─────────────────────────┴────┴────┴────┴────┴─────┴─────┴────┴────┴─────┴────────┘
最后，所有人都支付了相等的金额，但支付义务不同的情况后来得到解决:应该支付相同的费用，但支付不同的费用:
┌──────────┬──┬──┬──┬──┬──┬──┬──┬──┬─────┐
│Guy │1 │2 │3 │4 │5 │6 │7 │8 │Total│
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Should pay│10│10│10│10│10│10│10│10│80 │
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤
│Payed │7 │20│10│5 │10│10│6 │12│80 │
└──────────┴──┴──┴──┴──┴──┴──┴──┴──┴─────┘
小营业额:
54 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬────┬────┬────┬─────┬─────┬────┬────┬────┬─────┬────────┐
│Guy # │1 │8 │7 │4 │2 │3 │5 │6 │Total│Turnover│
├─────────────────────────┼────┼────┼────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Should pay │10 │10 │10 │10 │10 │10 │10 │10 │80 │ │
├─────────────────────────┼────┼────┼────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Has paid │7 │12 │6 │5 │20 │10 │10 │10 │80 │ │
├─────────────────────────┼────┼────┼────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Gets from the one to left│0.00│3.00│1.00│5.00 │10.00│0.00│0.00│0.00│ │19 │
├─────────────────────────┼────┼────┼────┼─────┼─────┼────┼────┼────┼─────┼────────┤
│Pays to the one to right │3.00│1.00│5.00│10.00│0.00 │0.00│0.00│0.00│ │19 │
└─────────────────────────┴────┴────┴────┴─────┴─────┴────┴────┴────┴─────┴────────┘
如何进行计算
当我们用蛮力完成时，这意味着生成参与者人数的所有排列。这可能是棘手的部分。例如，下面的(1,2,3,4)的所有排列都在下面(逐列编写，以提高可读性):
1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4
2 2 3 3 4 4 1 1 3 3 4 4 1 1 2 2 4 4 1 1 2 2 3 3
3 4 2 4 2 3 3 4 1 4 1 3 2 4 1 4 1 2 2 3 1 3 1 2
4 3 4 2 3 2 4 3 4 1 3 1 4 2 4 1 2 1 3 2 3 1 2 1
您最好搜索这一代。如果它发生在循环中就可以了。关键是您可以一次访问一列(如果行是行，则可以访问一行)。
伪:
// NOTE: The data is written as arrays
// For example "0 0 0 0" implies a 4-element array (vector) of integers
// Of course there may be other number of participants ("guys"),
// then we need "other-element" arrays, for example 7-element ones
// The code below may require additional looping
ToPay = 100 100 100 100 // Topmost example in this answer
HasPayed = 0 0 0 400 // Ditto
// Calculate debt
// This probably requires a loop from 1...4
Debt[n] = ToPay[n] - HasPayed[n] // Debt is now: 100 100 100 -300
smallest = 9999999 // Sufficiently big initial value
:For Row :In [each permutation of (1 2 3 4) // Row is now for example: 2 4 3 1
Test = Debt[Row] // Test is now for example: 100 -300 100 100
Accu = [4-element vector of zeroes]
Accu[1] = Row[1]
minimum = Row[1]
s = 2
:Repeat
Accu[s] = Accu[s-1] + Row[s]
minimum = min(minimum, Accu[s]) // We simply grab the smalles element in Accu
s += 1
:Until (s > 4)
// As this is ready, Accu may contain eg. 100 -200 -100 0
// and minimum would then contain -200
sum = 0
t = 1
:Repeat
Accu[t] -= minimum
sum += Accu[t]
t += 1
:Until (t > 4)
// When ready, Accu would be eg. 300 0 100 200
// and sum would be 300+0+100+200, ie. 600
:If (sum < smallest)
[store Row as best so far, for example into "BestRow"]
[store Accu, for example into BestAccu"]
smallest = sum
:End
:End
现在
从左到右)，例如1 2 3 4(= 1付2，2付3，3付4，4付1)。
人们可能会为“最佳方式”应用其他标准，但是这种解决方案可以最大程度地减少“四处走动”的金额，并使交易保持为每人一次付款。
还要注意的是，存在多个“最佳解决方案”，其中一个排列产生的最小周转率与另一个排列产生的最小周转率相同。对于最后一个示例，同样好(最好到最差)的解决方案的数目是:
48 96 144 144 240 240 480 336 672 432 768 912 960 768 1296 864 1392 1104 1200 1056 1488 1488 1488 1200 1344 1152 1776 1056 1344 1056 1152 1152 1344 768 1104 768 1056 720 912 480 672 528 528 240 576 288 432 192 288 144 240 48 96 48
...表示48个“最佳解决方案”，96个“次佳解决方案”，依此类推。
编辑:
有人告诉我，我曾错误地假设过一个标准:一个人只能从另一个人那里得到金钱。情况并非如此，任何人都可以仅向另一人提供钱，但是可以从一个人，一个人或多个人获得的钱。
事实证明，上面给出的解决方案已经接近完成。要解决这一新情况，只需要多处理一点结果即可。即，上述逻辑中现在存在的积累，其中连续多个人可能会积累越来越多的钱，而他们自己为积累做贡献，以偿还支付了大笔款项的人(“X先生”) -需要取消此积累，以便将其积累部分直接从付给，付给X，而不是通过其他参与者支付。
考虑这种情况:
┌──────────┬──┬──┬──┬──┬──┬──┬─────┐
│Guy │1 │2 │3 │4 │5 │6 │Total│
├──────────┼──┼──┼──┼──┼──┼──┼─────┤
│Should pay│10│10│20│30│10│20│100 │
├──────────┼──┼──┼──┼──┼──┼──┼─────┤
│Payed │35│0 │25│0 │0 │40│100 │
└──────────┴──┴──┴──┴──┴──┴──┴─────┘
尽管它看起来很简单，但是由于它是循环的，因此很难通过人头计算来解决。通过较早的方法，我们得到“累积”答案:
22 solutions with unique transfer sums. Best solution:
┌─────────────────────────┬──┬──┬──┬──┬──┬──┬─────┬────────┐
│Guy # │1 │3 │2 │5 │6 │4 │Total│Turnover│
├─────────────────────────┼──┼──┼──┼──┼──┼──┼─────┼────────┤
│Should pay │10│20│10│10│20│30│100 │ │
├─────────────────────────┼──┼──┼──┼──┼──┼──┼─────┼────────┤
│Has paid │35│25│0 │0 │40│0 │100 │ │
├─────────────────────────┼──┼──┼──┼──┼──┼──┼─────┼────────┤
│Gets from the one to left│30│5 │0 │10│20│0 │ │65 │
├─────────────────────────┼──┼──┼──┼──┼──┼──┼─────┼────────┤
│Pays to the one to right │5 │0 │10│20│0 │30│ │65 │
└─────────────────────────┴──┴──┴──┴──┴──┴──┴─────┴────────┘
然后我们可以解决每个债务，这是第二行-第三行(债务为正):
┌───┬──┬──┬──┬───┬──┐
│-25│-5│10│10│-20│30│
└───┴──┴──┴──┴───┴──┘
使用它，我们可以解决称为“累积-第五行-债务”的问题:
┌──┬─┬─┬──┬──┬─┐
│30│5│0│10│20│0│
└──┴─┴─┴──┴──┴─┘
由此，我们可以确定哪些付款方式可能会从“向右付款”更改为“付款人#n”-这可以通过比较累积的对并将比较的最后一个元素与首先(因为这个问题是循环的)。第一个比较是(30
┌─┬─┬─┬─┬─┬─┐
│0│0│1│1│0│1│
└─┴─┴─┴─┴─┴─┘
1表示下一次累积的金额大于当前累积的金额-这些是现在可以直接定向到#n的付款。
#n是谁？ #n是之后的下一个家伙。插槽3和4(上面第一个答案中的＃2和＃5人)后面是＃6人-他是＃2和＃5现在付款的人，而其他付款保持不变。
这个代码不是很棘手，但是取决于语言，因此我将其留给实现者。只需在每组中向右前进时减少累积，直到一组中的每个零(最多包括零)，然后重新确定付款地址即可。答案很漂亮:
┌──────────┬──┬──┬──┬──┬──┬──┐
│Guy │1 │3 │2 │5 │6 │4 │
├──────────┼──┼──┼──┼──┼──┼──┤
│Should pay│10│20│10│10│20│30│
├──────────┼──┼──┼──┼──┼──┼──┤
│Payed │35│25│0 │0 │40│0 │
├──────────┼──┼──┼──┼──┼──┼──┤
│Pays to │3 │ │6 │6 │ │1 │
├──────────┼──┼──┼──┼──┼──┼──┤
│Amount │5 │ │10│10│ │30│
└──────────┴──┴──┴──┴──┴──┴──┘
答案很有趣，因为实际上是“多付人”的第一个人必须向第三个人支付5美元。发生这种情况的原因是，第4个人(最右边)的债务为30，他必须向一个人付款-这会导致向“1”支付“超额付款”，但是由于＃1的邻居＃3需要从某处获取5， 1传递给他。然后其余的就完全适合了，＃6从＃2和＃5获得了他的20。标准是最小化付款并找到最佳解决方案，对吗？ :-)
一些示例(情况和解决方案)。低于2个均等付款人:
┌──────────┬──┬──┬──┬─┬─┬──┬──┬──┬─────┐ ┌───────┬─┬─┬──┬──┬─┬─┬──┬──┐
│Guy │1 │2 │3 │4│5│6 │7 │8 │Total│ │Guy │1│5│6 │8 │2│4│7 │3 │
├──────────┼──┼──┼──┼─┼─┼──┼──┼──┼─────┤ ├───────┼─┼─┼──┼──┼─┼─┼──┼──┤
│Should pay│7 │11│13│8│5│10│12│14│80 │ │Pays to│ │2│2 │2 │ │1│1 │1 │
├──────────┼──┼──┼──┼─┼─┼──┼──┼──┼─────┤ ├───────┼─┼─┼──┼──┼─┼─┼──┼──┤
│Payed │40│40│0 │0│0│0 │0 │0 │80 │ │Amount │ │5│10│14│ │8│12│13│
└──────────┴──┴──┴──┴─┴─┴──┴──┴──┴─────┘ └───────┴─┴─┴──┴──┴─┴─┴──┴──┘
一个大和一些小付款人:
┌──────────┬──┬───┬──┬──┬──┬──┬──┬──┬──┬──┬─────┐ ┌───────┬─┬──┬──┬──┬──┬──┬──┬─┬──┬─┐
│Guy │1 │2 │3 │4 │5 │6 │7 │8 │9 │10│Total│ │Guy │1│3 │7 │4 │10│6 │8 │2│5 │9│
├──────────┼──┼───┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤ ├───────┼─┼──┼──┼──┼──┼──┼──┼─┼──┼─┤
│Should pay│10│10 │10│12│10│19│11│33│6 │12│133 │ │Pays to│2│2 │2 │2 │2 │2 │2 │ │9 │1│
├──────────┼──┼───┼──┼──┼──┼──┼──┼──┼──┼──┼─────┤ ├───────┼─┼──┼──┼──┼──┼──┼──┼─┼──┼─┤
│Payed │5 │112│0 │0 │0 │1 │0 │0 │15│0 │133 │ │Amount │6│10│11│12│12│18│33│ │10│1│
└──────────┴──┴───┴──┴──┴──┴──┴──┴──┴──┴──┴─────┘ └───────┴─┴──┴──┴──┴──┴──┴──┴─┴──┴─┘
非常不规则:
┌──────────┬──┬──┬──┬──┬──┬──┬──┬──┬─┬──┬─────┐ ┌───────┬──┬──┬─┬─┬─┬─┬─┬──┬──┬─┐
│Guy │1 │2 │3 │4 │5 │6 │7 │8 │9│10│Total│ │Guy │1 │10│4│9│5│3│6│7 │8 │2│
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─┼──┼─────┤ ├───────┼──┼──┼─┼─┼─┼─┼─┼──┼──┼─┤
│Should pay│10│10│5 │12│10│19│11│33│6│12│128 │ │Pays to│10│ │9│5│3│ │2│2 │2 │ │
├──────────┼──┼──┼──┼──┼──┼──┼──┼──┼─┼──┼─────┤ ├───────┼──┼──┼─┼─┼─┼─┼─┼──┼──┼─┤
│Payed │7 │50│10│10│6 │12│1 │10│7│15│128 │ │Amount │3 │ │2│1│5│ │7│10│23│ │
└──────────┴──┴──┴──┴──┴──┴──┴──┴──┴─┴──┴─────┘ └───────┴──┴──┴─┴─┴─┴─┴─┴──┴──┴─┘
如我们所见，该解决方案看起来非常理想。
关于algorithm - 有效分担费用后偿还债务: max 1 transaction per person，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37162443/