4

私は問題を解決しようとしています（phpでは、プログラミング言語は関係ありません）。お金を払った人がn人いて、n人が支払った金額の合計と同じ金額を支払う人がm人います。これらの人の間の送金の最短ルートを計算したいと思います。支払いを分割して、別の人に支払うことが可能です。理想は、1人が1つまたは2つのトランザクションのみを行うことです。誰かが私を正しい方向に向けたり、これを手伝ってくれるかもしれませんか？

例：Aさんが100ドルを支払った

Bさんは200ドルを支払いました

Cさんは50ドルを支払いました

Dさんは24ドルを支払います

Eさんは175ドルを支払います

Fさんは151ドルを支払います

これに対する1つの可能な解決策は

人物Eは人物Aに100ドルを支払います。

EさんはBさんに75ドルを支払います。

FさんはBさんに125ドルを支払います。

FさんはCさんに26ドルを支払います

DさんはCさんに24ドルを支払います

4

1 に答える 1

2

理論的には、これは最適化問題として組み立てることができます。

基本的に、問題の構造を列挙し、初期値をシードし、指定したとおりにすべてのお金を割り当てるようにする一連の制約を確立します。

初期条件の制約：

A_paid = 100
B_paid = 200
C_paid = 50
D_out  = 24
E_out  = 175
F_out  = 151

支払われる金額は、利用可能な金額を超えることはできません:(私たちは人から人へD_to_A支払われる金額を保持する変数として定義します）DA

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困難であるため、これは予想外ではありません。

于 2010-08-22T13:37:30.037 に答える