算法完成羣組成員中的許多交易，至少沒有。步驟

假設我們有一個情況如下：算法完成羣組成員中的許多交易，至少沒有。步驟

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

算法完成羣組成員中的許多交易，至少沒有。步驟

回答

相關問題