谁欠谁钱优化 [英] Who owes who money optimization

问题描述

假设你有 n 个人，每个人都互相欠钱.一般来说，应该可以减少需要发生的交易量.即如果 X 欠 Y 4 英镑，Y 欠 X 8 英镑，那么 Y 只需要支付 X 4 英镑(1 笔交易而不是 2 笔).

Say you have n people, each who owe each other money. In general it should be possible to reduce the amount of transactions that need to take place. i.e. if X owes Y £4 and Y owes X £8, then Y only needs to pay X £4 (1 transaction instead of 2).

当 X 欠 Y 时，这变得更加困难，但 Y 也欠着 X 的 Z.我可以看到您可以轻松计算出一个特定的周期.当我将其视为一个完全连接的图时，这对我很有帮助，边是每个人所欠的金额.

This becomes harder when X owes Y, but Y owes Z who owes X as well. I can see that you can easily calculate one particular cycle. It helps for me when I think of it as a fully connected graph, with the edges being the amount each person owes.

问题似乎是 NP-complete，但是我可以制定什么样的优化算法来减少总交易量?不必那么高效，因为 N 对我来说很小.

Problem seems to be NP-complete, but what kind of optimisation algorithm could I make, nevertheless, to reduce the total amount of transactions? Doesn't have to be that efficient, as N is quite small for me.

这个问题的目的是能够在会计系统中有一些东西可以在每个人登录时告诉他们你可以通过简单地支付某人 X 金额和其他人 Y 金额来删除 M 笔交易".因此，银行解决方案(尽管如果每个人都同时付款是最佳选择)在这里不能真正使用.

The purpose of this problem would be to be able to have in the accounting system something that can say to each person when they log in "You can remove M amount of transactions by simply paying someone X amount, and someone else Y amount". Hence the bank solution (though optimal if everyone is paying at the same time) cannot really be used here.

推荐答案

人们是否需要通过向某人​​支付他们实际欠个人的钱来清偿他们的债务?如果没有，以下似乎很容易可疑地工作:

Are people required to clear their debts by paying somebody that they actually owe money to personally? If not, the following seems to work suspiciously easily:

对于每个人，计算出他们应该支付或应该收到的净额.

For each person, work out the net amount they should pay, or should receive.

让欠钱的人付钱给应该收钱的人net min(欠款，应收金额).在此之后，至少两个参与者中的一个不欠也不应该得到任何东西，因此可以从问题中删除.

Have somebody who owes money net pay somebody who should receive money net min(amount owed, amount to be received). After this, at least one of the two participants owes nothing and should receive nothing, and so can be removed from the problem.

假设我遗漏了什么，适用的限制条件是什么(或犯的严重错误)?

Assuming I have missed something, what are the constraints that apply (or gross error made)?

这篇关于谁欠谁钱优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！