C++で友人間の貸し借りのキャッシュフローを最小化するアルゴリズムを解説

問題の概要

友人同士でお金の貸し借りを行っていると、グループ内に複数の資金の流れ(キャッシュフロー)が発生します。本記事では、このキャッシュフローを最小限に抑える方法を解説します。

例として、P1、P2、P3という3人の友人がいるとしましょう。彼らの間の資金の流れは、以下の図のようになっています。

この状態ではまだ資金の流れが最適化されていません。そこで、貸し借りを整理・統合すると、最終的には次のようなシンプルな流れになります。

貪欲法(グリーディーアプローチ)による解法

この問題は貪欲法を用いて効率的に解くことができます。基本的な考え方は、「各ステップで1人の人物の金額を完全に清算し、残りのn-1人について再帰的に同じ処理を繰り返す」というものです。

では、最初にどの人物を選べばよいのでしょうか。その答えが純額(ネット金額)の計算です。純額とは、その人が受け取るべきすべての債権から、支払うべきすべての債務を差し引いた値のことです。純額を全員分計算したら、その中から最大値と最小値を持つ2人を見つけます。この2人が、それぞれ「最も多く受け取るべき債権者」と「最も多く支払うべき債務者」に該当します。そして、最小値を持つ人物から順に清算を進めていきます。

アルゴリズムの手順

• 各人物 Pi(i = 0 〜 n-1)に対して、以下のステップを実行します。
• 全員の純額を計算します。人物 i の純額は「債権の合計」から「債務の合計」を引いた値として求められます。
• 最大の債権者 Pc と最大の債務者 Pd を特定します。最大債権者が受け取るべき金額を max_credit、最大債務者が支払うべき金額を max_debit と呼びます。
• x := min(max_credit, max_debit) を求め、Pd から x を減算し、Pc に x を加算します。
• x が max_credit と等しい場合、Pc を対象の集合から取り除き、残りの n-1 人について再帰的に処理を続けます。
• x が max_debit と等しい場合、Pd を対象の集合から取り除き、残りの n-1 人について再帰的に処理を続けます。

この手順により、1回の清算ごとに少なくとも1人が完全に精算されるため、全体の送金回数は必ず n-1 回以下に収まります。

C++による実装例

#include<iostream>
#include<algorithm>
#define N 3
using namespace std;
int getMinIndex(int arr[]) {
    int minInd = 0;
    for (int i=1; i<N; i++)
       if (arr[i] < arr[minInd])
       minInd = i;
    return minInd;
}
int getMaxIndex(int arr[]) {
    int maxInd = 0;
    for (int i=1; i<N; i++)
       if (arr[i] > arr[maxInd])
       maxInd = i;
    return maxInd;
}
void cashFlowTask(int amount[]) {
    int max_credit = getMaxIndex(amount), max_debit = getMinIndex(amount);
    if (amount[max_credit] == 0 && amount[max_debit] == 0)
    return;
    int min_val = min(-amount[max_debit], amount[max_credit]);
    amount[max_credit] -= min_val;
    amount[max_debit] += min_val;
    cout << "P" << max_debit << " sends " << min_val << " to " << "P" << max_credit << endl;
    cashFlowTask(amount);
}
void minCashFlow(int graph[][N]) {
    int amount[N] = {0};
    for (int p=0; p<N; p++)
    for (int i=0; i<N; i++)
    amount[p] += (graph[i][p] - graph[p][i]);
    cashFlowTask(amount);
}
int main() {
    int graph[N][N] = {
    {0, 1000, 2000},
    {0, 0, 5000},
    {0, 0, 0}};
    minCashFlow(graph);
}

コードのポイントを簡単に整理すると、minCashFlow 関数では隣接行列 graph をもとに各人の純額を算出し、cashFlowTask 関数がその純額配列を受け取って、最大債権者と最大債務者の間で可能な限りの金額を清算しながら再帰的に処理を進めます。全員の純額がゼロになった時点で再帰が終了します。

実行結果

P1 sends 4000 to P2
P0 sends 3000 to P2

この出力から、元々3件あった貸し借り(P1→P2: 2000、P1→P2: 1000相当、P2→P3: 5000など)が、わずか2件の送金にまとめられていることが分かります。このように貪欲法を使うことで、友人間の資金のやり取りを最小回数・最小手数で清算できるのです。