这是一种更通用的问题，不是特定于语言的。更多关于想法和算法的使用。
系统如下：
它记录朋友群体之间的小额贷款。Alice并且Bill要去吃午饭，比尔的卡坏了，所以爱丽丝付了他的饭钱，10 美元。
第二天在火车站见面，Chales 没钱买票，所以Bill给他买了一张，5 美元。那天晚些时候，她向朋友借了 5美元和 1 美元，给她的朋友买了礼物。CharlesBillAliceCharlesBill
现在，假设他们都在系统中注册了该交易，它看起来像这样：
Alice -> Bill $10
Bill -> Alice $1
Bill -> Charles $5
Charles -> Alice $5
所以，现在，唯一需要做的就是Bill给Alice她 4 美元（他给了她 1 美元，然后Charlie 把他的 5美元转给了她Alice），他们处于初始状态。
如果我们将其扩展到许多不同的人，进行多笔交易，那么获得尽可能少的交易的最佳算法是什么？
这实际上看起来像是复式会计概念可以帮助的工作。
您的交易可以构造为簿记条目，因此：
Alice Bill Charles Balance
Alice -> Bill $10 10 10- 0 0
Bill -> Alice $1 9 9- 0 0
Bill -> Charles $5 9 4- 5- 0
Charles -> Alice $5 4 4- 0 0
你有它。在每笔交易中，您贷记一个分类帐并借记另一个分类帐，以便余额始终为零。最后，您只需计算出应用于每个帐户的最少交易数量，即可将其归零。
对于这个简单的案例，这是从比尔到爱丽丝的简单 4 美元转账。您需要做的是将至少一个帐户（但最好是两个）减少到零，以添加每笔交易。假设你有更复杂的：
Alice Bill Charles Balance
Alice -> Bill $10 10 10- 0 0
Bill -> Alice $1 9 9- 0 0
Bill -> Charles $5 9 4- 5- 0
Charles -> Alice $5 4 4- 0 0
Charles -> Bill $1 4 5- 1 0
那么所需的交易将是：
Bill -> Alice $4 0 1- 1 0
Bill -> Charles $1 0 0 0 0
不幸的是，在某些州，这种简单的贪婪策略并不能产生最佳解决方案（j_random_hacker感谢指出这一点）。一个例子是：
Alan Bill Chas Doug Edie Fred Bal
Bill->Alan $5 5- 5 0 0 0 0 0
Bill->Chas $20 5- 25 20- 0 0 0 0
Doug->Edie $2 5- 25 20- 2 2- 0 0
Doug->Fred $1 5- 25 20- 3 2- 1- 0
显然，这可以在四步中逆转（因为到达那里只需要四步）但是，如果您不明智地选择了第一步(Edie->Bill $2)，那么您将逃脱的最低限度是五步。
您可以使用以下规则解决此特定问题：
这将导致以下序列：
Alan->Bill $5。Chas->Bill $20。然而，这仅仅是因为可能性很小。随着人数的增加和群体的相互关系变得更加复杂，您很可能需要进行详尽的搜索才能找到所需的最少移动次数（基本上是上面的规则 1、2 和 3，但经过扩展以处理更多深度） .
我认为这是在所有情况下为您提供最少数量的交易所需要的。但是，最好的答案可能并不需要（最好，在这种情况下，意味着最大的“每块钱”）。可能即使是基本的 1/2/3 规则集也会为您的目的提供足够好的答案。
直观地说，这听起来像是一个 NP 完全问题（它简化为一个非常类似于装箱的问题），但是下面的算法（装箱的一种修改形式）应该是相当不错的（没有时间证明，抱歉）。
清除每个人的头寸，即从您上面的示例中：
爱丽丝 = $4 比尔 = $-4 查尔斯 = $0
所有净债权人从高到低排序，所有债务人从低到高排序，然后通过遍历列表进行匹配。
在某些时候，您可能需要拆分一个人的债务以将所有东西都净掉 - 在这里最好拆分成尽可能大的块（即首先放入剩余空间最多的垃圾箱）。
这将需要 O(n log n) 之类的东西（再次，需要适当的证明）。
有关更多信息，请参阅分区问题和装箱问题（前者是一个非常相似的问题，如果您将自己限制为固定精度事务，那么它是等价的 - 当然需要证明）。
我创建了一个 Android 应用程序来解决这个问题。您可以在旅途中输入费用，它甚至会建议您“谁应该支付下一个”。最后它计算“谁应该向谁发送多少”。我的算法计算所需的最小交易数量，您可以设置“交易容差”，这可以进一步减少交易（您不关心 1 美元的交易）试试看，它被称为 Settle Up：
https://market.android.com/details?id=cz.destil.settleup
我的算法描述：
我有解决 n-1 事务问题的基本算法，但它不是最优的。它的工作原理是这样的：从付款中，我计算每个成员的余额。余额是他支付的金额减去他应该支付的金额。我越来越根据平衡对成员进行排序。然后我总是选择最贫穷和最富有的，然后进行交易。其中至少有一个余额为零，并被排除在进一步的计算之外。有了这个，事务的数量不能比 n-1 差。它还最大限度地减少了交易中的金额。但这不是最优的，因为它没有检测到可以在内部建立的子组。
很难找到可以在内部安定下来的子群体。我通过生成所有成员组合并检查子组中的余额总和是否为零来解决它。我从 2 对开始，然后是 3 对 ... (n-1) 对。组合生成器的实现是可用的。当我找到一个子组时，我使用上述基本算法计算子组中的事务。对于每个找到的子组，都会保留一个事务。
解决方案是最优的，但复杂度增加到 O(n!)。这看起来很糟糕，但诀窍是实际上只有少数成员。我在 Nexus One（1 Ghz 处理器）上对其进行了测试，结果是：直到 10 个成员：<100 毫秒，15 个成员：1 秒，18 个成员：8 秒，20 个成员：55 秒。所以直到 18 个成员执行时间都很好。超过 15 个成员的解决方法可以是仅使用基本算法（它快速且正确，但不是最优的）。
源代码：
源代码可在一份关于用捷克语编写的算法的报告中找到。源代码在最后，它是英文的：
http://www.settleup.info/files/master-thesis-david-vavra.pdf
我找到了一个在 Excel 中实现的实用解决方案：
找出谁欠的最多
让那个人把他欠的全部钱还给应该得到最多的人
这使得第一人称为零
考虑到 (n-1) 人之一的金额发生变化，重复此过程
它应该会导致最多 (n-1) 次转账，而好处是没有人做超过一笔付款。以 jrandomhacker 的（修改后的）示例为例：
a=-5 b=25 c=-20 d=3 e=-2 f=-1（总和应该为零！）
c -> b 20. 结果：a=-5 b=5 c=0 d=3 e=-2 f=-1
a -> b 5 结果：a=0 b=0 c=0 d=3 e=-2 f=-1
e -> d 2 结果 a=0 b=0 c=0 d=1 e=0 f=-1
f -> d 1
现在，每个人都很满意，没有人会为两次或多次付款而烦恼。如您所见，一个人可能会收到不止一笔付款（在本例中为人 d）。
我设计了一个解决方案，使用与此处提到的方法有些不同的方法。它使用问题的线性规划公式，取自 Compressed Sensing 文献，尤其是Donoho 和 Tanner (2005) 的这项工作。
我写了一篇描述这种方法的博客文章，以及一个实现它的微型 R 包。我很想从这个社区得到一些反馈。
干杯。
好吧，第一步是完全忽略交易。把它们加起来。你真正需要知道的是一个人欠/拥有的债务净额。
通过创建一个疯狂的流程图并找到最大流量，您可以很容易地找到交易。然后一刀切...
部分阐述：每个人都有一个源节点、一个汇节点和一个节点。除了源节点和汇节点之间没有边外，每对节点之间都会有一条边。人与人之间的边缘在两个方向上都有无限的容量。从源节点到人的边的容量等于该人的净债务（如果他们没有净债务，则为 0）。从人员节点到汇节点的边的容量等于该人员所欠的净金额（如果他们没有净欠款，则为 0）。
应用最大流量和/或最小切割将为您提供一组转移。实际流量将是多少资金将被转移。
只有当某人欠了超过 2 个人，也欠同一个集合时，你才能从简单集合中减少交易数量。
也就是说，简单的设置只是找到每个余额并偿还它。不超过N！交易。
如果 A 欠 B 和 C，并且 BC 的某个子集相互欠，所以 B 欠 C，那么代替：A -> B，A -> C（3 笔交易）。您将使用：A -> B，B -> C（2 个事务）。
所以换句话说，您正在构建一个有向图，并且您想要修剪顶点以最大化路径长度并最小化总边。
抱歉，我没有适合你的算法。
您应该能够在 O(n) 中解决这个问题，首先确定每个人的欠款和欠款多少。将任何欠他欠债的人的债务转移给他的债务人（从而把那个人变成一个终点）。重复直到你不能再转移任何债务。
这是我为解决 Java 中此类问题而编写的代码。我不是 100% 确定这是否提供了最少的交易数量。代码的清晰度和结构可以改进很多。
在这个例子中：
约翰在杂货上花了 100 美元。杂货被鲍勃和爱丽丝吃掉了。
import java.util.*;
public class MoneyMinTransactions {
static class Expense{
String spender;
double amount;
List<String> consumers;
public Expense(String spender, double amount, String... consumers){
this.spender = spender;
this.amount = amount;
this.consumers = Arrays.asList(consumers);
}
}
static class Owed{
String name;
double amount;
public Owed(String name, double amount){
this.name = name;
this.amount = amount;
}
}
public static void main(String[] args){
List<Expense> expenseList = new ArrayList<>();
expenseList.add(new Expense("Sarah", 400, "Sarah", "John", "Bob", "Alice"));
expenseList.add(new Expense("John", 100, "Bob", "Alice"));
//make list of who owes how much.
Map<String, Double> owes = new HashMap<>();
for(Expense e:expenseList){
double owedAmt = e.amount/e.consumers.size();
for(String c : e.consumers){
if(!e.spender.equals(c)){
if(owes.containsKey(c)){
owes.put(c, owes.get(c) + owedAmt);
}else{
owes.put(c, owedAmt);
}
if(owes.containsKey(e.spender)){
owes.put(e.spender, owes.get(e.spender) + (-1 * owedAmt));
}else{
owes.put(e.spender, (-1 * owedAmt));
}
}
}
}
//make transactions.
// We need to settle all the negatives with positives. Make list of negatives. Order highest owed (i.e. the lowest negative) to least owed amount.
List<Owed> owed = new ArrayList<>();
for(String s : owes.keySet()){
if(owes.get(s) < 0){
owed.add(new Owed(s, owes.get(s)));
}
}
Collections.sort(owed, new Comparator<Owed>() {
@Override
public int compare(Owed o1, Owed o2) {
return Double.compare(o1.amount, o2.amount);
}
});
//take the highest negative, settle it with the best positive match:
// 1. a positive that is equal to teh absolute negative amount is the best match.
// 2. the greatest positive value is the next best match.
// todo not sure if this matching strategy gives the least number of transactions.
for(Owed owedPerson: owed){
while(owes.get(owedPerson.name) != 0){
double negAmt = owes.get(owedPerson.name);
//get the best person to settle with
String s = getBestMatch(negAmt, owes);
double posAmt = owes.get(s);
if(posAmt > Math.abs(negAmt)){
owes.put(owedPerson.name, 0.0);
owes.put(s, posAmt - Math.abs(negAmt));
System.out.println(String.format("%s paid %s to %s", s, Double.toString((posAmt - Math.abs(negAmt))), owedPerson.name));
}else{
owes.put(owedPerson.name, -1 * (Math.abs(negAmt) - posAmt));
owes.put(s, 0.0);
System.out.println(String.format("%s paid %s to %s", s, Double.toString(posAmt), owedPerson.name));
}
}
}
}
private static String getBestMatch(double negAmount, Map<String, Double> owes){
String greatestS = null;
double greatestAmt = -1;
for(String s: owes.keySet()){
double amt = owes.get(s);
if(amt > 0){
if(amt == Math.abs(negAmount)){
return s;
}else if(greatestS == null || amt > greatestAmt){
greatestAmt = amt;
greatestS = s;
}
}
}
return greatestS;
}
}
如果您将状态作为图的节点，那么您将能够使用最短路径算法来知道答案。