Cân bằng tài khoản tối ưu trong C++

Một nhóm bạn đi du lịch và vay mượn lẫn nhau. Giao dịch (x, y, z) nghĩa là người x cho người y $z. Tìm số giao dịch tối thiểu để thanh toán tất cả nợ.

Ví dụ: [[0,1,10], [2,0,5]] → Kết quả = 2. Người #0 cho #1 $10, #2 cho #0 $5. Cách thanh toán: #1 trả #0 và #2 mỗi người $5.

Phương pháp giải

Tính số dư (balance) của mỗi người: người cho tiền bị trừ, người nhận tiền được cộng. Thu được mảng các số dư khác 0. Sử dụng DFS/backtracking: thử gán nợ của người idx cho người i có dấu ngược chiều, đệ quy tìm số giao dịch tối thiểu.

Ví dụ chương trình

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector 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>& t) {
        map m;
        int n = t.size();
        for (int i = 0; i < n; i++) {
            int u = t[i][0], v = t[i][1], bal = t[i][2];
            m[u] += bal;
            m[v] -= bal;
        }
        for (auto& p : m) if (p.second) v.push_back(p.second);
        return min(dfs(0), (int)v.size());
    }
};

int main() {
    Solution ob;
    vector> v = {{0,1,10}, {2,0,5}};
    cout << ob.minTransfers(v);
    return 0;
}

Đầu vào

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

Đầu ra

2