C++でお互いからお金を借りてきた特定の友人のセット間のキャッシュフローを最小限に抑える

友達が少ないとしましょう。彼らはお互いからお金を借りてきました。したがって、ネットワークにはある程度のキャッシュフローがあります。私たちの仕事は、ネットワークのキャッシュフローを最小限に抑えることです。 P1、P2、P3の3人の友達がいるとします。それらの間のキャッシュフローは以下のようです-

このキャッシュフローは最小ではありません。最小化する必要があります。その場合、最終的な図は次のようになります-

この問題を解決するために、貪欲なアプローチを使用します。ここで、各ステップで1人のすべての金額を決済し、残りのn-1人に対して繰り返します。さて、問題は、最初の人をどのように選ぶかということです。答えは、すべてのクレジットからすべての負債を差し引いて正味額が得られるすべての人の正味額を計算することです。正味額を評価するときは、最小値と最大値の2つのノードを見つけます。これらの2人は、ほとんどの債権者と債務者です。最小値の人が最初の人です。アルゴリズムは以下のようになります-

• 0からn– 1までのすべての人のPiについて、次の手順を実行します

• すべての人の正味金額を計算します。人の正味額は、すべてのクレジットの合計からすべての負債の合計を差し引くことで計算できます。

• 最大債権者Pcと最大債務者Pdを見つけます。最大債権者に貸方記入される最大金額がmax_creditであり、最大債務者から借方に記入される最大金額がmax_debitと呼ばれるとします。

• x：=max_creditとmax_debitの最小値を設定します。次に、xをPdから借方に記入し、xをPcに貸方記入します

• xがmax_creditと同じである場合は、セットからPcを削除し、次のn-1人に対して繰り返します。

• xがmax_debitと同じである場合は、一連の人からPdを削除し、次のn-1人に対して繰り返します

例

#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);
}

出力

P1 sends 4000 to P2
P0 sends 3000 to P2