3人が旅行の費用に貢献したとします。アダムはホテルに150ドル、ボブはガスに60ドル、チャーリーは120ドルの食事を提供します。旅行の後、彼らは費用のバランスを取りたいと思っています。
簡単な解決策は、各費用を3人に分割し、他の参加者が最初に商品を購入した参加者に個別に支払うことです。
当然、アダムがボブに20ドルを借り、ボブがアダムに50ドルを借りている場合、それはボブがアダムに30ドルを支払うことに相当します。この論理を続けると、ボブはアダムに30ドル、チャーリーに20ドル、チャーリーはアダムに10ドルを借りています。
ここに落とし穴があります：この解決策は最適ではありません。トランザクション数を減らすことができます。最初にボブからチャーリーに、次にチャーリーからアダムに支払われる10ドルの金額があります。代わりに、ボブはすでにアダムに支払っている金額にその10ドルを追加することができます。
最終的に、ボブはチャーリーに10ドル、アダムに40ドルを支払います。今では誰もが同じ金額の110ドルで費用を賄っています。
私の質問は次のとおりです。
費用とトランザクションの絶対最小量とのバランスをとる方法を見つけることが目標である場合、n人のアクターによるこの問題の一般的な解決策は何ですか？最も多くの借金があるために最も多くからパスをトラバースすると、計算コストが高くなる可能性があるため、簡単ではありません。
NP完全問題をこの問題に還元することはできますか？
この問題のよく知られた名前はありますか？