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

Question

假设三个人支付了一次旅行的费用：亚当支付了旅馆的费用，150 美元，鲍勃支付了汽油，60 美元，查理提供了食物，120 美元。旅行结束后，他们想平衡开支。

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

自然，如果亚当欠鲍勃 20 美元，而鲍勃欠亚当 50 美元，则相当于鲍勃欠亚当 30 美元。继续这个逻辑，鲍勃欠亚当 30 美元，欠查理 20 美元，查理欠亚当 10 美元。

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

最后，鲍勃向查理支付了 10 美元，向亚当支付了 40 美元。现在每个人都支付了等量的 110 美元的费用。

---

我的问题是：

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

• NP完全问题可以简化为这个问题吗？

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

Answer 1

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

Answer 2

是的，这是子集和问题。