算法完成群组成员中的许多交易，至少没有。步骤

假设我们有一个情况如下：算法完成群组成员中的许多交易，至少没有。步骤

A has to give $10 to B. 
B has to give $20 to C. 
C has to give $10 to D.

现在这种情况可以简化如下：

A loses $10 i.e A=-10 
B gains $10 from B but loses $20 to C i.e B=-10 
C gains $20 from B but loses $10 to D i.e c=10 
D gains $10 i.e D=10

因此，该交易可以简化为： A给出了$ 10 C和B给出10美元给D。

另一个例子：

A gives $1 to B. 
B gives $1 to C. 
C gives $1 to D.

这可以简化为： A给出了$ 1 D.

以类似的方式，以上面的例子，我想作一个计算机程序，找出完成任何给定交易的最简单方法。但我无法为此设备算法。如果有人有这个想法，请帮助我。谢谢。

来源

2016-09-20 dreadedHarvester

如果你只是想为这个问题的算法改变[标签：C]标签为[标签：语言不可知]。 – tversteeg

如果你想在C中使用一个解决方案，那么你首先必须告诉我们你做了什么，试过了什么，以及你的代码有什么问题。请[请阅读如何提出良好问题]（http://stackoverflow.com/help/how-to-ask），并学习如何创建[最小，完整和可验证示例]（http：// stackoverflow。 COM /帮助/ MCVE）。 –

您可以将此模型作为有向图进行建模，计算每个节点的净流出量，对于所有+ ve流出的节点，收集它们的资金，然后分配给剩余的。 –

我可以建议以下ALGO：

指定对于每个用户的阵列和用于他们的交易的阵列。示例：user = [A,B,C,D]; sum = [0,0,0,0];
更新每次交易的总数列举示例：[-10,10,0,0] -> [-10,-10,20,0] -> [-10,-10,10,10]
使用任何复杂度为O（nlogn）的算法对数组进行排序。同时更新用户数组。
找到sum数组中的负和正结点（理想情况下，您可以在排序过程中存储它，或者可以执行二分搜索）。
接下来，将sum数组中的负值分配到正值中。示例：在我们的例子中，排序后的sum数组将与原始[-10,-10,10,10]相同，正负结是sum数组的第二个索引。所以我们开始在sum[i] into sum[2 + i]的循环中进行分配，并找出总和中的过量或不足，并在下一次迭代中对其进行调整。

来源

2016-09-20 13:48:01

算法完成群组成员中的许多交易，至少没有。步骤

回答

相关问题