假设你有n个人,每个人都欠对方钱一般来说,应该可以减少需要进行的交易量即,如果X欠Y 4英镑,Y欠X 8英镑,则Y只需支付X 4英镑(1笔交易,而不是2笔交易)。
当x欠y时,这会变得更困难,但是y欠z也欠x。我可以看出你可以很容易地计算出一个特定的周期当我把它看作一个完全连通的图时,它对我有帮助,边是每个人欠下的钱。
问题似乎是NP完全的,但是我可以用什么样的优化算法来减少事务总量呢不必那么有效率,因为对我来说n很小。
编辑:
这个问题的目的是能够在会计系统中有一些东西,可以在每个人登录时对他们说“你可以通过简单地向某人支付x金额,而其他人支付y金额来删除m金额的交易”。因此,银行的解决方案(尽管如果每个人同时付款是最优的)不能真正在这里使用。
最佳答案
人们是否需要通过向某人支付他们实际欠下的钱来还清他们的债务如果不是,那么下面的操作似乎很容易让人怀疑:
对于每个人,计算出他们应该支付或应该收到的净金额。
有谁欠了钱净付谁应该收到钱净分(欠款,收到金额)。在这之后,两个参与者中至少有一个不欠任何东西,也不应该得到任何东西,因此可以从问题中消除。
假设我漏掉了一些东西,那么应用的约束条件是什么(或者犯了严重的错误)?