相关疑难解决方法(0)

问题

我最近被要求计算一起去旅行的一群人所欠的钱,并且遇到了一个有趣的问题:假设你知道每个人欠另一个人的金额,那么巩固人与人之间债务的一般算法是什么？这样只需要支付最少的款项？以此为例:

• 迈克欠约翰100
• 约翰欠雷切尔200
• 迈克欠雷切尔400

我们可以通过重新制定这样的债务来取消迈克和约翰之间的付款:

• 迈克欠约翰0
• 约翰欠Rachel 100
• 迈克欠雷切尔500

我手工完成了数学计算,因为它很容易,但是后来我的程序员很想找到一个通用的算法来为一个任意大的组做这个.这对我来说似乎是一个图算法,所以我将其重新表示为图:

以图表形式查看

• 顶点是组中的人
• 边缘由所欠的金额定向和加权.例如,从Mike到Rachel的重量为500的边缘意味着Mike欠Rachel 500.
• 约束:每个节点的净重和必须保持不变.
• 目标是找到具有仍满足约束的最小边数的图.