Ý tưởng: dùng thực tế rằng cách Tham lam (Greedy) cho giải tối ưu cho bài toán Ba lô phân số (Fractional Knapsack).
Kiểm tra nút có cho giải pháp tốt hơn không: tính giải pháp tối ưu (qua nút) dùng Greedy. Nếu Greedy cho kết quả <= best so far, không thể có giải tốt hơn qua nút này.
Thuật toán hoàn chỉnh:
- Sắp xếp vật phẩm giảm dần theo tỷ lệ giá trị/trọng lượng để tính upper bound bằng Greedy.
- Khởi tạo maxProfit = 0.
- Tạo hàng đợi Q rỗng.
- Tạo nút giả (dummy) cây quyết định, đưa vào Q. Lợi nhuận và trọng lượng = 0.
- Lặp khi Q không rỗng:
- Lấy nút u từ Q.
- Tính lợi nhuận nút cấp tiếp theo. Nếu > maxProfit, cập nhật maxProfit.
- Tính bound nút cấp tiếp theo. Nếu > maxProfit, thêm nút vào Q.
- Xét trường hợp không lấy nút cấp tiếp theo: thêm nút vào Q với level tiếp theo, trọng lượng/lợi nhuận không thay đổi.
Minh họa:
Đầu vào
The maximum possible profit = 235