การชำระหนี้ที่เหมาะสมที่สุดใน C++

สมมติว่ากลุ่มเพื่อนไปเที่ยวกันและบางครั้งก็ยืมเงินกัน เช่น อมิตจ่ายค่าอาหารกลางวันให้บิคราม 10 ดอลลาร์ ต่อมาชاندانให้อมิต 5 ดอลลาร์ค่าแท็กซี่ เราต้องออกแบบโมเดลที่แต่ละธุรกรรมเป็นทูเพิล (x, y, z) หมายถึงคน x ให้คน y จำนวน z ดอลลาร์

สมมติว่าอมิต บิคราม และชاندانคือคนที่ 0, 1, 2 ตามลำดับ ธุรกรรมสามารถแทนได้เป็น [[0,1,10], [2,0,5]] หากเรามีรายการธุรกรรมระหว่างกลุ่มคน เราต้องหาจำนวนธุรกรรมขั้นต่ำที่จำเป็นเพื่อชำระหนี้ให้สิ้นสุด

เช่น ถ้าอินพุตคือ [[0,1,10], [2,0,5]] ผลลัพธ์จะเป็น 2 เพราะคน #0 ให้คน #1 10 ดอลลาร์ แล้วคน #2 ให้คน #0 5 ดอลลาร์ ต้องใช้ 2 ธุรกรรม วิธีหนึ่งในการชำระหนี้คือ คน #1 จ่ายคน #0 และ #2 คนละ 5 ดอลลาร์

ในการแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:

• กำหนดอาร์เรย์ v
• กำหนดฟังก์ชัน dfs() รับ idx: ret := inf; while idx < v.size() และ v[idx]==0: idx++; ลูป i จาก idx+1 ถึง v.size()-1: ถ้า v[i]*v[idx] < 0: v[i] += v[idx]; ret = min(ret, 1 + dfs(idx+1)); v[i] -= v[idx]; คืนค่า (ret==inf ? 0 : ret)
• จาก main method: สร้าง map m, นับยอดคงเหลือ (balance) ของแต่ละคนจากธุรกรรม แล้วนำยอดที่ไม่เป็นศูนย์ใส่ v คืนค่า min(dfs(0), v.size())

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#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 it = m.begin(); it != m.end(); it++) {
            if (it->second) v.push_back(it->second);
        }
        return min(dfs(0), (int)v.size());
    }
};
main() {
    Solution ob;
    vector> v = {{0,1,10},{2,0,5}};
    cout << (ob.minTransfers(v));
}

อินพุต

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

เอาต์พุต

2