Trong hệ thống quản lý chuỗi cung ứng (Supply Chain Management), làm thế nào để áp dụng chiến lược Greedy trong bài toán tìm trạm xăng tối ưu (Gas Station / Circular Route) nhằm giảm thiểu số lần dừng chân của xe vận chuyển hàng hóa?

Question

Accepted Answer

Bản chất cơ chế hoạt động
Bài toán yêu cầu tìm điểm xuất phát trên một tuyến đường vòng tròn sao cho phương tiện có thể hoàn thành chu trình mà không bị cạn kiệt nhiên liệu. Chiến lược tham lam dựa trên nguyên lý: nếu tổng lượng nhiên liệu lớn hơn tổng chi phí di chuyển trên toàn tuyến thì chắc chắn có lời giải, và bất kỳ trạm nào làm cho mức nhiên liệu tích lũy tụt xuống dưới 0 đều không thể là điểm xuất phát.
Phân tích chi tiết

Theo dõi tổng nhiên liệu dư thừa toàn cục total_tank và nhiên liệu dư thừa hiện tại của đoạn đường đang xét current_tank.
Nếu tại trạm i, current_tank nhỏ hơn 0, điều này có nghĩa là tất cả các trạm từ điểm xuất phát cũ cho đến trạm i đều không thể làm điểm khởi hành hợp lệ. Ta tiến hành đặt lại điểm xuất phát mới là i + 1 và reset current_tank = 0.
Độ phức tạp thời gian chỉ là O(N) với một vòng lặp duy nhất.

Ví dụ code minh họa (TypeScript)
function canCompleteCircuit(gas: number[], cost: number[]): number {
    let totalTank = 0;
    let currentTank = 0;
    let startingStation = 0;

for (let i = 0; i < gas.length; i++) {
        const netGain = gas[i] - cost[i];
        totalTank += netGain;
        currentTank += netGain;

// Nếu nhiên liệu hiện tại âm, không thể đi tiếp từ startingStation hiện tại
        if (currentTank < 0) {
            startingStation = i + 1;
            currentTank = 0;
        }
    }

return totalTank >= 0 ? startingStation : -1;
}

// Kiểm tra thực tế
console.log(canCompleteCircuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])); // Output: 3
Lưu ý kinh nghiệm thực chiến
Đây là bài toán phỏng vấn phổ biến tại các doanh nghiệp công nghệ lớn. Lập trình viên cấp độ Junior thường dễ mắc lỗi viết các vòng lặp lòng nhau (nested loops) dẫn đến độ phức tạp O(N^2). Việc áp dụng tư duy Greedy một chiều giúp tối ưu hiệu năng đáng kể cho các hệ thống backend có khối lượng dữ liệu lớn.

Trong hệ thống quản lý chuỗi cung ứng (Supply Chain Management), làm thế nào để áp dụng chiến lược Greedy trong bài toán tìm trạm xăng tối ưu (Gas Station / Circular Route) nhằm giảm thiểu số lần dừng chân của xe vận chuyển hàng hóa?

Bản chất cơ chế hoạt động

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ủ đề