Tối thiểu hóa dòng tiền giữa nhóm bạn vay mượn lẫn nhau trong C++

Giả sử có một nhóm bạn vay mượn lẫn nhau, tạo ra dòng tiền phức tạp. Mục tiêu là tối thiểu hóa số giao dịch (cash flow) trong mạng lưới.

Ví dụ 3 người P1, P2, P3 với dòng tiền ban đầu:

Sau khi tối thiểu hóa:

Thuật toán tham lam: mỗi bước giải quyết hết số dư của một người, đệ quy cho n-1 người còn lại. Chọn người có số dư ròng (net amount) nhỏ nhất (nợ nhiều nhất) và lớn nhất (được nợ nhiều nhất). Số dư ròng = tổng được nợ - tổng nợ.

Các bước:

• Tính số dư ròng cho mỗi người.
• Tìm người nợ nhiều nhất (max_debit) và được nợ nhiều nhất (max_credit).
• X = min(|max_debit|, max_credit). Người nợ trả X cho người được nợ.
• Nếu X = max_credit, loại người được nợ ra khỏi tập hợp, đệ quy n-1 người.
• Nếu X = |max_debit|, loại người nợ ra khỏi tập hợp, đệ quy n-1 người.

Ví dụ

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

Kết quả

P1 sends 4000 to P2 P0 sends 3000 to P2