最近,我一直在阅读Splitwise问题,在该问题中,一群人之间彼此之间有债务,而目标是以最少的交易数来偿还这些债务。也可以将其建模为要减少边缘的有向加权图。
[我最常遇到的解决方案是greedyiterativealgorithm,它首先计算每个人的净结果(欠他的钱-他欠的钱),然后重复以下步骤:
1. take max. debtor X and max. creditor Y
2. if X owes more than Y is owed
then X pays Y Y's value
reduce X's debt by Y's value
set Y's value to 0
else X pays Y X's value
reduce Y's value by X's debt
set X's debt to 0
...直到每个人的值都是0。
我的问题:
看来此算法不是最佳算法。考虑情况[-3,-2,-2、3、4],其中正表示债权人,负表示债权人。使用所描述的算法,我们需要四个交易操作才能消除所有债务:
>> [-3, -2, -2, 3, 4]
>> [0, -2, -2, 3, 1] ([0] pays [4])
>> [0, 0, -2, 1, 1] ([1] pays [3])
>> [0, 0, -1, 1, 0] ([2] pays [4])
>> [0, 0, 0, 0, 0] ([2] pays [3])
但是您可以看到可以通过三笔交易来清算债务:欠款$ 3的人支付贷方$ 3,然后两个欠款$ 2的人分别向欠债者$ 4支付。
实际上,我相信所描述的算法的目标是使交易的总金额最小化,而不是使交易的数量最小化,该交易可以做到并且可以证明(尽管我在这里不会尝试)。