php - 结合连续背包问题和可变尺寸装箱问题的算法

Question

我正在尝试解决一个问题(在 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 美元

Answer 1

理论上这可以被定义为一个优化问题:

基本上，我们将建立一组约束条件来枚举您的问题结构，为初始值设置种子，并确保我们按照您的指示分配所有资金。

初始条件约束:

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，所以这并不意外。