我正在尝试解决一个问题(在 php 中,但编程语言无关紧要)。 我有 n 个人已经付了钱,我有 m 个人将支付与以下金额相同的金额n 人已经付款。 我想计算这些人之间汇款的最短路线。可以分开付款并支付给不同的人。 理想的情况是一个人只进行一两次交易。 有人可以指出我正确的方向或帮助我吗?
一个例子: A 支付了 100 美元
B 支付了 200 美元
C 支付了 50 美元
D 将支付 $24
E 将支付 $175
F 将支付 $151
一个可能的解决方案是
E 支付 100 美元给 A,
E 支付 75 美元给 B,
F 支付 $125 给 B,
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,所以这并不意外。
关于php - 结合连续背包问题和可变尺寸装箱问题的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3541619/