优化需要的分配算法

今天我在和朋友解释我上次旅程的旅行费用时，遇到了一个有趣的问题。优化需要的分配算法

假设我们有下列支出：

# expenditures in US-$ 
Peter= 117 
Joe= 38 
Bill= 15 
Chris= 0 
Alan= 209 
Tim= 201 
Ahmet= 124 
Pati= 57 
Steven= 74

现在，我们已经决定，每个人都应该支付的钱一样多。鉴于平均支出为92.77778 US- $，余额是这样的：

# balances in US-$ 
Peter= 24.22 
Joe= -54.78 
Bill= -77.78 
Chris= -92.78 
Alan= 116.22 
Tim= 108.22 
Ahmet= 31.22 
Pati= -35.78 
Steven=-18.78

所以现在我想找到我们共有银行交易的最低数量和公平地分配份额的优化方法的交易（所以两个优化目标）

我抬头看Stable Marriage Problem，但我认为它不适用于这种情况。

来源

2014-01-23 Joschi

这似乎不是一个难题 - 按照上升的支出对参与者进行排序，然后按顺序让每个参与者将他们的否定（当前）余额转移给下一个参与者。 n-1次交易，每个参与者最多一次交易。当然，其中的每一项都是您一般可以做的最好的。

还是有一些额外的限制我错过了？

来源

2014-01-23 10:59:57 Sneftel

打我吧:)。 +1。我只补充一点，这个解决方案没有考虑到，通常当你为某种东西进行筹码时，你支付的数额是10或5的倍数。在这种特殊情况下，你可以获得比n更好的结果-1，因为例如来自另外两个人的2笔交易可能会同时覆盖他们的正面和负面余额。 –

考虑有2 * 5 = 10个人。其中5个每个都有-1个余额，其中5个每个都有+1个余额。交易的最佳数量是5.您的算法将如何工作？ –

这就是我的意思是关于“一般情况”。在给出的例子中，没有办法低于n-1交易。如果这就是乔希寻找的东西，但我认为有一个非常简单的方法可以做到这一点。（基本上，子集总和的动态规划算法的变化。） – Sneftel

该方法仅解决“银行交易总额最小数量”的部分。

人们分为两类，比如Giver（其余额为负）和Receiver（其余额为正）。

关键观察在一个最佳的解决方案中，给予者应该总是给钱，接收者应该总是收到钱。人A不可能把钱给B，然后B给C一些钱。

现在来解决问题。

While (there is some giver or receiver) { 
    Find the giver with the largest balance, say A. 
    Find the receiver with the largest balance, say B. 
    Let A gives as much money as B needs. 
    Delete Person if his/her balance becomes 0. 
}

来源

2014-01-23 12:51:50

优化需要的分配算法

回答

相关问题