Fra*_*cis 20 algorithm math optimization graph
假设你有n个人,每个人都欠他们的钱.通常,应该可以减少需要进行的交易量.即如果X欠Y£4而Y欠X£8,那么Y只需要支付X£4(1个交易而不是2个).
当X欠Y时,这变得更难,但Y欠欠Z的是谁.我可以看到你可以很容易地计算出一个特定的周期.当我把它看作一个完全连通的图形时,它对我有帮助,边缘是每个人所欠的金额.
问题似乎是NP完全的,但是我可以做出什么样的优化算法来减少交易总量？不一定非常有效,因为N对我来说非常小.
编辑:
这个问题的目的是能够在会计系统中拥有一些可以在每个人登录时说出来的内容"你可以通过简单地向某人支付X金额,以及其他人Y金额来删除M笔交易金额".因此,银行解决方案(尽管每个人都在同一时间支付,但是最佳)在这里无法真正使用.
人们是否需要通过向某人支付他们实际欠个人钱的方式来清偿债务？如果没有,以下似乎很容易怀疑:
对于每个人,计算他们应该支付或应该收到的净额.
有钱欠净的人应该收到一个应该收钱的人(欠款,金额).在此之后,两个参与者中至少有一个没有任何东西,应该什么都不收,所以可以从问题中删除.
假设我错过了一些东西,那么适用的约束(或粗略错误)是什么？
我认为你需要建立一个不同的数据结构（一棵树，每次一个人是根节点），它将检查每个人可以“杀死”多少“交易”，然后选择最好的一个，进行循环，然后再次重建它。它不是 o(N)，但我认为它是 N^2，并且它不会给你最好的结果。这只是一种策略。