ลด Cash Flow ระหว่างเพื่อนที่ยืมเงินกันใน C++

สมมติมีกลุ่มเพื่อนที่ยืมเงินกัน จะมี Cash Flow ในเครือข่าย เราต้องลด Cash Flow ให้น้อยที่สุด ตัวอย่าง 3 คน P1, P2, P3 มี Cash Flow ดังภาพ:

Cash Flow นี้ไม่ใช่ค่าต่ำสุด หลังลดแล้วจะเป็นแบบนี้:

ใช้ Greedy Approach: ทุกขั้นตอนจัดการยอดของคนหนึ่งแล้ว Recur สำหรับ n-1 คนที่เหลือ เลือกคนแรกอย่างไร? คำนวณ Net Amount ของทุกคน (Credits - Debts) หา Maximum Creditor และ Maximum Debtor คนที่มีค่า Min เป็นคนแรก

อัลกอริทึม:

1. คำนวณ Net Amount ทุกคน
2. หา Max Creditor (Pc) และ Max Debtor (Pd)
3. กำหนด x = min(max_credit, max_debit) Debit x จาก Pd Credit x ให้ Pc
4. ถ้า x = max_credit ลบ Pc ออก และ Recur สำหรับ n-1 คน
5. ถ้า x = max_debit ลบ Pd ออก และ Recur สำหรับ 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);
}

ผลลัพธ์

P1 sends 4000 to P2 P0 sends 3000 to P2