连续背包问题和可变尺寸装箱问题相结合的算法
我正在尝试解决一个问题（在 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 美元
I'm trying to solve a problem (in php, but programming language doesn't matter).
I'm having a n number of persons that have paid money, and I have got a m number of persons that are going to pay the same amount as the sum of what the n number of people have paid.
I want to calculate the shortest route of money transfers between these persons. It is possible to split the payments and pay to different persons.
The ideal is that one person only makes one or two transactions.
Can someone maybe point me in the right direction or help me with this?
An example:
person A has paid $100
person B has paid $200
person C has paid $50
person D will pay $24
person E will pay $175
person F will pay $151
One possible solution to this is
person E pays $100 to person A,
person E pays $75 to person B,
person F pays $125 to person B,
person F pays $26 to person C
person D pays $24 to person C
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
理论上，这可以被视为一个优化问题：
基本上，我们将建立一组约束，枚举问题的结构，播种初始值，并确保我们按照您的指示分配所有资金。
初始条件约束：
支付的金额不能超过可用金额：（我们将
D_to_A定义为保存从D人支付给A人的金额的变量>）支付给每个人的金额必须等于他们已经支付的金额：
如果我们现在停下来并将其作为线性程序来解决，我们会找到跨越整个变量空间的任何解决方案，但您希望最小化实际付款的数量。我们可以通过与上述约束一致地最小化所有
X_to_Y变量来做到这一点。您可以使用您最喜欢的优化技术来解决问题，有很多可用的线性程序求解器，我喜欢 lpsolve。
虽然这解决了您描述的具体示例，但很容易看出如何通过添加更多变量将其扩展到更大的问题......但是随着您添加人员，问题的复杂性会大大增加。如果我没记错的话，背包问题是 NP 或 NP 难问题，所以这并不意外。
In theory this could be framed as an optimization problem:
Basically we're going to establish a set of constraints that enumerate the structure of your problem, seed the initial values, and make sure that we allocate all the money as you've indicated.
Initial condition constraints:
Amount paid out cannot exceed the amount available: (we define
D_to_Aas a variable holding the amount paid from personDto personA)Amount paid to each individual must be equal to what they've already paid:
If we were to stop now and solve this as a linear program we'd find any solution spanning the entire variable space, but you're looking to minimize the number of actual payments. We can do this by minimizing over all
X_to_Yvariables in concert with the constraints above.You can use your favorite optimization technique to solve the problem, there's plenty of available linear program solvers, I like lpsolve.
Though this solves the specific example you described it's easy to see how it can be expanded to larger problems by adding more variables...but the problem grows in complexity substantially as you add people. If I recall correctly the knapsack problem is NP or NP-hard, so this isn't unexpected.