Trong hệ thống xử lý giao dịch tài chính, làm thế nào để áp dụng thuật toán Greedy trong bài toán Phân phối Tiền thối (Minimum Number of Coins) khi hệ thống tiền tệ có mệnh giá chuẩn để giảm thiểu số lượng tờ tiền trả lại cho khách hàng?

Question

Accepted Answer

Bản chất bài toán
Bài toán đổi tiền (Coin Change Problem) yêu cầu tìm số lượng ít nhất các đồng tiền có mệnh giá cho trước để tạo ra một tổng giá trị tiền tệ cụ thể. Đối với hệ thống tiền tệ tiêu chuẩn (như USD, VND), chiến lược Greedy hoạt động rất hiệu quả.
Chiến lược Greedy

Sắp xếp danh sách các mệnh giá tiền theo thứ tự giảm dần.
Lựa chọn mệnh giá lớn nhất có thể mà nhỏ hơn hoặc bằng số tiền còn lại cần thối.
Lặp lại quá trình cho đến khi số tiền cần thối về bằng 0.

Ví dụ cài đặt mã nguồn (JavaScript)
function getMinCoins(coins, amount) {
    // Sắp xếp mệnh giá giảm dần
    coins.sort((a, b) => b - a);

let result = [];
    let remainingAmount = amount;

for (let i = 0; i < coins.length; i++) {
        while (remainingAmount >= coins[i]) {
            remainingAmount -= coins[i];
            result.push(coins[i]);
        }
    }

if (remainingAmount > 0) {
        return "Không thể đổi được số tiền này với các mệnh giá hiện có";
    }

return result;
}

// Ví dụ sử dụng
const coins = [1, 5, 10, 25];
const amount = 63;
console.log(getMinCoins(coins, amount)); // Kết quả: [25, 25, 10, 3]
Lưu ý kinh nghiệm thực chiến

Chiến lược Greedy chỉ đúng đắn tuyệt đối với hệ thống mệnh giá chính tắc (Canonical Coin Systems). Nếu hệ thống mệnh giá không chuẩn (ví dụ: [1, 3, 4] và cần đổi số tiền 6), thuật toán Greedy sẽ chọn [4, 1, 1] (tổng 3 đồng) trong khi kết quả tối ưu thực tế là [3, 3] (tổng 2 đồng). Trong trường hợp đó, lập trình viên phải chuyển sang sử dụng Quy hoạch động (Dynamic Programming).

Bản chất bài toán

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi greedy algorithms liên quan cùng chủ đề