我正在尝试解决一个问题（在 php 中，但编程语言无关紧要）。我有n个人支付了钱，我有m个人将支付与n个人支付的总和相同的金额。我想计算这些人之间的最短汇款路线。可以拆分付款并支付给不同的人。理想的情况是一个人只进行一两次交易。有人可以指出我正确的方向或帮助我吗？
示例：A 支付了 100 美元
B 人支付了 200 美元
C 人支付了 50 美元
D 将支付 24 美元
E 人将支付 175 美元
F 人将支付 151 美元
一种可能的解决方案是
E 人向 A 人支付 100 美元，
E 人向 B 人支付 75 美元，
F 人向 B 人支付 125 美元，
F 人向 C 人支付 26 美元
D 人向 C 人支付 24 美元
从理论上讲，这可以被视为一个优化问题：
基本上，我们将建立一组约束来枚举您的问题的结构，播种初始值，并确保我们按照您的指示分配所有资金。
初始条件约束：
A_paid = 100
B_paid = 200
C_paid = 50
D_out = 24
E_out = 175
F_out = 151
支付的金额不能超过可用的金额：（我们定义D_to_A为持有人D对人支付金额的变量A）
D_out >= D_to_A + D_to_B + D_to_C
E_out >= E_to_A + E_to_B + E_to_C
F_out >= F_to_A + F_to_B + F_to_C
支付给每个人的金额必须等于他们已经支付的金额：
A_paid = D_to_A + E_to_A + F_to_A
B_paid = D_to_B + E_to_B + F_to_B
C_paid = D_to_C + E_to_C + F_to_C
如果我们现在停止并将其作为线性程序来解决，我们会找到跨越整个变量空间的任何解决方案，但您正在寻求最小化实际支付的数量。我们可以通过最小化X_to_Y与上述约束一致的所有变量来做到这一点。
min: D_to_A + D_to_B + D_to_C + ...
您可以使用您最喜欢的优化技术来解决问题，有很多可用的线性程序求解器，我喜欢lpsolve。
尽管这解决了您描述的特定示例，但很容易看出如何通过添加更多变量将其扩展到更大的问题……但是随着人员的增加，问题的复杂性会大大增加。如果我没记错的话，背包问题是 NP 或 NP-hard，所以这并不意外。