Bài 21: Chia tiền nhóm sao cho ít lần chuyển khoản nhất? Thuật toán tham lam

Đi dã ngoại 6 người, mỗi người trả một khoản: người trả tiền xe, người trả tiền ăn, người mua nước… Cuối chuyến, ai phải chuyển cho ai bao nhiêu để ít lần chuyển khoản nhất? Bài toán quen thuộc này hóa ra ẩn chứa cả một bài toán khó của khoa học máy tính.

Bài thứ hai mươi mốt của chuyên mục "Thuật toán trong đời sống": chia tiền nhóm, thuật toán tham lam và giới hạn của máy tính.

1. Bước 1: tính số dư của từng người

Mẹo quan trọng: không cần quan tâm "ai trả cho món gì". Chỉ cần tính số dư của mỗi người = số tiền đã trả − phần mình phải chịu. Người dư dương cần được nhận lại tiền, người dư âm cần trả tiền. Tổng tất cả số dư luôn bằng 0.

2. Bước 2: thuật toán tham lam

Lặp lại: lấy người nợ nhiều nhất trả cho người được nhận nhiều nhất, số tiền bằng giá trị nhỏ hơn trong hai người. Sau mỗi lần, ít nhất một người được "xóa sổ". Vì vậy với n người, thuật toán dùng tối đa n − 1 lần chuyển khoản.

Chia tiền nhóm bằng thuật toán tham lam

#include <bits/stdc++.h>
using namespace std;
int main(){
    // Số dư của từng người sau chuyến đi (nghìn đồng): dương = được nhận, âm = phải trả
    vector<pair<string,long long>> bal = {{"An",350},{"Binh",90},{"Chi",-10},
                                          {"Dung",-90},{"Em",-130},{"Phuc",-210}};
    priority_queue<pair<long long,string>> cred, debt;   // max-heap
    for(auto& [p, b] : bal){ if(b > 0) cred.push({b, p}); if(b < 0) debt.push({-b, p}); }
    int cnt = 0;
    while(!cred.empty() && !debt.empty()){
        auto [c, cp] = cred.top(); cred.pop();
        auto [d, dp] = debt.top(); debt.pop();
        long long x = min(c, d);                          // ghép hai người "lớn" nhất
        cout << dp << " -> " << cp << ": " << x << "\n"; cnt++;
        if(c > x) cred.push({c - x, cp});
        if(d > x) debt.push({d - x, dp});
    }
    cout << "So lan chuyen khoan: " << cnt << "\n";
}

import heapq

# Chuyến dã ngoại của 6 bạn: (người trả, số tiền nghìn đồng, những người cùng dùng)
bills = [("An", 600, "An Binh Chi Dung Em Phuc"),     # thuê xe
         ("Binh", 300, "An Binh Chi Dung Em Phuc"),   # ăn trưa
         ("Chi", 240, "An Chi Dung Em"),              # vé tham quan
         ("Dung", 180, "Binh Dung Phuc"),             # nước uống
         ("Em", 120, "An Chi Em")]                    # kem

bal, pairs = {}, set()
for payer, money, users in bills:
    users = users.split()
    for u in users:
        bal[u] = bal.get(u, 0) - money / len(users)
        if u != payer: pairs.add((u, payer))           # cách "ngây thơ": ai nợ ai thì trả người đó
    bal[payer] = bal.get(payer, 0) + money
print("Cach ngay tho:", len(pairs), "lan chuyen khoan")

# Tham lam: người nợ nhiều nhất trả cho người được nhận nhiều nhất
cred = [(-b, p) for p, b in bal.items() if b > 0.5]
debt = [(b, p) for p, b in bal.items() if b < -0.5]
heapq.heapify(cred); heapq.heapify(debt)
moves = []
while cred and debt:
    c, cp = heapq.heappop(cred); d, dp = heapq.heappop(debt)
    x = min(-c, -d)
    moves.append(f"{dp} -> {cp}: {x:.0f}")
    if -c - x > 0.5: heapq.heappush(cred, (c + x, cp))
    if -d - x > 0.5: heapq.heappush(debt, (d + x, dp))
print("Tham lam:", len(moves), "lan chuyen khoan")
for m in moves: print("  ", m)

Kết quả chạy (bản Python):

Cach ngay tho: 17 lan chuyen khoan
Tham lam: 4 lan chuyen khoan
   Phuc -> An: 210
   Em -> An: 130
   Dung -> Binh: 90
   Chi -> An: 10

Nếu ai nợ ai thì trả thẳng người đó (cách "ngây thơ"), nhóm cần 17 lần chuyển khoản. Thuật toán tham lam chỉ cần 4 lần. Bản C++ dùng sẵn bảng số dư và cho cùng kết quả.

3. Ứng dụng thật: Splitwise

Ứng dụng chia tiền Splitwise có tính năng "Simplify debts" – theo mô tả trên App Store, tính năng này đơn giản hóa các khoản nợ thành kế hoạch trả tiền dễ nhất. Thuật toán cụ thể mà Splitwise dùng không được công bố.

4. Bất ngờ: tìm số lần chuyển khoản ít nhất là bài toán NP-khó

Tham lam cho kết quả tốt nhưng không phải lúc nào cũng tối ưu. Các nhà nghiên cứu (Verhoeff, 2004; Pătcaş và Bartha) đã chỉ ra bài toán tìm số lần chuyển khoản ít nhất là NP-khó – nghĩa là đến nay chưa ai biết thuật toán nhanh nào giải đúng mọi trường hợp với số người lớn.

Ý tưởng tối ưu: nếu chia được nhóm thành nhiều nhóm nhỏ có tổng số dư bằng 0, mỗi nhóm k người chỉ cần k − 1 lần chuyển. Trong ví dụ, Binh (+90) và Dung (−90) tạo thành một nhóm riêng, nên đáp án tối ưu là 6 − 2 = 4 lần – trùng với tham lam. Tìm cách chia nhiều nhóm nhất là phần "khó" của bài toán, gần với bài toán tổng tập con.

Với nhóm bạn dưới khoảng 15–20 người, ta vẫn có thể tìm đáp án tối ưu bằng quy hoạch động trên tập con (bitmask): thử mọi tập con có tổng bằng 0.

5. Bạn học được gì từ đây?

• Đơn giản hóa mô hình (chỉ giữ số dư) giúp bài toán dễ hơn rất nhiều.
• Hàng đợi ưu tiên (priority queue) giúp lấy nhanh phần tử lớn nhất.
• Có những bài toán đời thường lại thuộc loại khó nhất của tin học – biết điều đó giúp ta chọn giải pháp "đủ tốt".

Bài tập luyện tập

• CSES – Apple Division (chia tập con – làm quen với độ khó kiểu tổng tập con)
• CSES – Elevator Rides (quy hoạch động bitmask)
• Viết chương trình quy hoạch động bitmask tìm số lần chuyển khoản tối ưu cho tối đa 15 người, rồi so với tham lam.

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 22: Bầu cử và các cách đếm phiếu – Nghịch lý Condorcet và định lý Arrow

Đọc tiếp: bầu cử & Condorcet →

← Bài trước: nén âm thanh & FourierXem tất cả 27 bài →

Nguồn tham khảo

• Verhoeff (2004) – Settling Multiple Debts Efficiently: An Invitation to Computing Science, Informatics in Education
• Pătcaş & Bartha – Debt Clearing (arXiv 1402.6556)
• App Store – Splitwise
• NUS CS3230 – Settling Debts (bài tập NP-đầy đủ)