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

问题描述

假设你有N多人，每个谁欠对方钱。一般它应当可以减少需要发生的交易量。即如果X欠Ÿ£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欠Ÿ困难，但ÿ欠ž谁欠X作为好。我可以看到你可以很容易地计算出一个特定的周期。它帮助我，当我把它看作是一个完全连通图，其边缘是每个人欠的金额。

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完全问题，但我可以做什么样的优化算法，不过，以减少总量的​​交易？不必是有效率的，如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量除去交易并购数量和别人ÿ量。因此，银行的解决方案（尽管最优的，如果每个人都付出在同一时间）能不能真正用在这里。

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.

有别人谁欠了谁应收款净额分钱净工资某人（所欠金额，金额可收）。在此之后，两个参与者中的至少一个欠什么，应该接收任何操作，并因此可以从问题中移除。

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屋！