algorithm - 平衡多个参与者之间的集体开支

Question

假设有三个人支付了一次旅行的费用:Adam 支付了 150 美元的旅馆费用，Bob 支付了 60 美元的汽油费，Charlie 提供了 120 美元的食物。旅行结束后，他们想平衡开支。

简单的解决方案是，每笔费用在三个人之间分摊，并由其他参与者单独支付给第一个购买商品的人。

自然地，如果 Adam 欠 Bob 20 美元，而 Bob 欠 Adam 50 美元，则这等同于 Bob 欠 Adam 30 美元。继续这个逻辑，Bob 欠 Adam 30 美元，欠 Charlie 20 美元，而 Charlie 欠 Adam 10 美元。

要注意的是:这个解决方案不是最优的。交易数量可以减少。有 10 美元首先从 Bob 支付给 Charlie，然后从 Charlie 支付给 Adam。相反，Bob 可以将这 10 美元添加到他已经支付给 Adam 的金额中。

最后，Bob 向 Charlie 支付 10 美元，向 Adam 支付 40 美元。现在每个人都支付了等额的 110 美元的费用。

---

我的问题是:

• 当目标是找到费用与绝对最小交易量的平衡方式时，n 个参与者对这个问题的一般解决方案是什么？从欠债最多的人到欠债最多的人遍历路径可能会变得计算量大，所以这不是微不足道的。

• 能否将一个 NP 完全问题简化为这个问题？

• 这个问题有一个众所周知的名字吗？

Answer 1

假设 c 人支付的金额超过了他们的份额(债权人)，d 人支付的金额少于他们的份额(债务人)。由于根据您的定义，如果解决方案意味着最少数量的交易，则该解决方案是最佳的，理想情况是每个债务人只需要进行一次转账(他们显然必须至少进行一次)。那么问题来了，欠债权人 1 的钱 X1 能否通过欠款金额的精确总和得到​​？ X2 能否通过剩余金额的精确求和得到？依此类推，直到 Xc。从这个意义上说，这个问题与子集和问题有关，正如 n.m. 所述(有点简洁)。