这是一种更通用的问题,不是特定于语言的.更多关于使用的想法和算法.
系统如下:
它在朋友群之间登记小额贷款.Alice并且Bill要去吃午饭,比尔的卡不工作,所以爱丽丝支付他的餐费,10美元.
第二天Bill,Charles在火车站相遇,Chales没有钱买票,所以Bill买了一个,5美元.那天晚些时候从她和朋友那里Alice借了5美元Charles和1美元Bill购买礼物.
现在,假设他们都在系统中注册了这些事务,它看起来像这样:
Alice -> Bill $10
Bill -> Alice $1
Bill -> Charles $5
Charles -> Alice $5
所以,现在,唯一需要做的就是Bill给Alice4美元(他给了她1美元并将他的5 美元Charlie 转移到Alicealredy)并且他们处于初始状态.
如果我们将这个扩展到许多不同的人,拥有多个事务,那么获得尽可能少的事务的最佳算法是什么？
我期待着针对以下问题的算法.
问题:会有一群人欠他们一些钱或没有钱.现在,我需要一个算法(最好和最好的)来解决这个群体中的费用.
Person AmtSpent
------ ---------
A 400
B 1000
C 100
Total 1500
现在,每人的费用是1500/3 = 500.意思是B给A 100.给B 400.我知道,我可以用最少的金额开始工作.
有人可以指出我最好的一个,如果你有.
提前致谢.
总结一下,1.找出总费用和人均费用.
2.找出欠款或欠款的金额(-ve表示未付款).
3.从最低+ ve量开始.将其分配给-ve金额.
4.继续重复步骤3,直到用完量为止.
秒.转到下一个更大的+ ve号码.继续重复3和4,直到有+ ve数字.
或者有更好的方法吗？我只是好奇.:)
比如说,我们有N多个账户有正余额B_1, ..., B_n.
我们可以进行转账T(from,to,amount),在账户之间取得一定的余额.
我们了解最佳的余额分配O_1, ..., O_n.
问题是:我们如何找到实现最佳分配的最小转移集？我们N-1最多可以获得转账吗？
例:
Balances {0}: 10, {1}: 40, {2}: 50
Optimal {0}: 20, {1}: 60, {2}: 20
T(2,0,10) => {0}: 20, {1}: 40, {2}: 40
T(2,1,20) => {0}: 20, {1}: 60, {2}: 20
我正在建立一个市场,我想为市场参与者订单建立一个匹配机制.
例如,我收到这些订单:
A buys 50
B buys 100
C sells 50
D sells 20
可以被表示为List<Orders>,其中Order是与一类Participant,BuySell和Amount
我想创建一个Match输出两件事的函数:
List<Order>)List<MatchedOrder>其中MatchOrder有Buyer,Seller,Amount约束是最小化订单数量(不匹配和匹配),同时不留下任何可能的匹配(即,最终只能存在无法匹配的买入或卖出订单)
所以在上面的例子中,结果将是:
A buys 50 from C
B buys 20 from D
B buys 80 (outstanding)
这似乎是一个相当复杂的编写算法,但在实践中很常见.任何指针在哪里看？