C++で解く最適なアカウントバランシング問題――最小回数の取引で債務を清算する方法

友人のグループが休暇に出かけ、旅先で互いにお金を貸し借りしていたとしましょう。例えば、AmitさんがBikramさんの昼食代として10ドルを立て替えました。その後、ChandanさんがAmitさんにタクシー代として5ドルを渡しました。このように、各取引をタプル(x, y, z)――つまり「人物xが人物yにzドル支払った」――という形で表現するモデルを設計することを考えます。

Amit、Bikram、Chandanをそれぞれ人物0、1、2とすると、上記の取引は [[0, 1, 10], [2, 0, 5]] と表せます。グループ内のメンバー間の取引リストが与えられたとき、すべての債務を清算するために必要となる最小の取引回数を求めるのが本問題です。

入力が [[0,1,10], [2,0,5]] の場合、出力は 2 になります。人物#0が人物#1に10ドルを渡し、その後人物#2が人物#0に5ドルを渡したためです。この債務を清算する一つの方法は、人物#1が人物#0と人物#2にそれぞれ5ドルずつ支払うことです。こうすれば、わずか2回の取引ですべてが精算できます。

解決のアプローチ

まず各人について純残高(ネットの収支)を計算します。「受け取った金額 − 立て替えた金額」を求め、残高が0の人は清算に関与しないため対象から除外します。残った正負の残高同士を組み合わせて相殺し、バックトラッキング(深さ優先探索)によって取引回数の最小値を探索します。

アルゴリズムの手順

• 配列 v を用意する
• 関数 dfs() を定義する(引数は idx)
• ret := inf(無限大)で初期化
• idx < vのサイズ かつ v[idx] が 0 である間、idx を1ずつ増やす
• i := idx + 1 から vのサイズ未満の間、i を1ずつ増やしながら:
  • v[i] * v[idx] < 0(符号が異なる=貸し借りの向きが逆)の場合:
    • v[i] := v[i] + v[idx](相殺を実行)
    • ret := min(ret, 1 + dfs(idx + 1))(取引1回を加えて再帰)
    • v[i] := v[i] − v[idx](状態を元に戻すバックトラック)
• ret が inf と等しければ 0 を、そうでなければ ret を返す
• mainメソッドでは以下を実行する:
• マップ m を1つ定義する
• n := t のサイズ
• i := 0 から i < n の間、i を1ずつ増やしながら:
  • u := t[i][0]、v := t[i][1]
  • bal := t[i][2]
  • m[u] := m[u] + bal
  • m[v] := m[v] − bal
• m 内の各キーと値のペア i について:
  • 値が 0 でない場合、その値を配列 v の末尾に追加する
• min(dfs(0), vのサイズ) を返す

C++での実装例

以下の実装を見ると、処理の流れがより理解しやすくなります。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector<int> v;
   int dfs(int idx) {
      int ret = INT_MAX;
      while (idx < v.size() && !v[idx])
         idx++;
      for (int i = idx + 1; i < v.size(); i++) {
         if (v[i] * v[idx] < 0) {
            v[i] += v[idx];
            ret = min(ret, 1 + dfs(idx + 1));
            v[i] -= v[idx];
         }
      }
      return ret == INT_MAX ? 0 : ret;
   }
   int minTransfers(vector<vector<int>>&t) {
      map<int, int> m;
      int n = t.size();
      for (int i = 0; i < n; i++) {
         int u = t[i][0];
         int v = t[i][1];
         int bal = t[i][2];
         m[u] += bal;
         m[v] -= bal;
      }
      map<int, int>::iterator i = m.begin();
      while (i != m.end()) {
         if (i->second)
            v.push_back(i->second);
         i++;
      }
      return min(dfs(0), (int)v.size());
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {{0,1,10},{2,0,5}};
   cout << (ob.minTransfers(v));
}

入力

{{0,1,10},{2,0,5}}

出力

2

計算量について

純残高の計算には取引数をNとしてO(N log N)(マップの操作を含む)かかります。一方、dfs()によるバックトラッキングは最悪情况下非効率ですが、残高が0でない人数が少ない現実的な規模の入力であれば十分高速に動作します。探索の枝刈りとして、残高が0の要素を事前に除外している点が重要です。