Bài toán cái túi phân số¶
Question
Cho \(n\) vật phẩm, trong đó trọng lượng của vật phẩm thứ \(i\) là \(wgt[i-1]\) và giá trị của nó là \(val[i-1]\), và một cái túi có sức chứa \(cap\). Mỗi vật phẩm chỉ có thể được chọn một lần, nhưng có thể chọn một phần của vật phẩm với giá trị tỷ lệ thuận với trọng lượng được chọn. Hỏi tổng giá trị lớn nhất có thể đặt vào cái túi dưới ràng buộc về sức chứa là bao nhiêu? Một ví dụ được thể hiện trong hình dưới đây.
Bài toán cái túi phân số (fractional knapsack problem) nhìn chung rất giống với bài toán cái túi 0-1 (0-1 knapsack problem), với các trạng thái bao gồm vật phẩm hiện tại \(i\) và sức chứa \(c\), và mục tiêu là tối đa hóa giá trị dưới sức chứa giới hạn của cái túi.
Điểm khác biệt là bài toán này cho phép chỉ chọn một phần của vật phẩm. Như thể hiện trong hình dưới đây, chúng ta có thể phân chia một vật phẩm một cách tùy ý và tính toán giá trị của nó tỷ lệ thuận với trọng lượng được chọn.
- Đối với vật phẩm \(i\), giá trị của nó trên mỗi đơn vị trọng lượng là \(val[i-1] / wgt[i-1]\), được gọi là giá trị đơn vị (unit value).
- Giả sử chúng ta đưa một phần của vật phẩm \(i\) có trọng lượng \(w\) vào cái túi, khi đó giá trị tăng thêm cho cái túi là \(w \times val[i-1] / wgt[i-1]\).
Xác định chiến lược tham lam¶
Việc tối đa hóa tổng giá trị trong cái túi về mặt bản chất có nghĩa là ưu tiên các vật phẩm có giá trị trên mỗi đơn vị trọng lượng cao hơn. Từ quan sát này, chúng ta có thể rút ra chiến lược tham lam như thể hiện trong hình dưới đây.
- Sắp xếp các vật phẩm theo giá trị đơn vị từ cao xuống thấp.
- Duyệt qua tất cả các vật phẩm, lựa chọn một cách tham lam vật phẩm có giá trị đơn vị cao nhất trong mỗi lượt.
- Nếu sức chứa còn lại của cái túi không đủ, hãy sử dụng một phần của vật phẩm hiện tại để lấp đầy cái túi.
Triển khai mã nguồn¶
Chúng ta định nghĩa một lớp Item để các vật phẩm có thể được sắp xếp theo giá trị đơn vị. Sau đó, chúng ta duyệt qua các vật phẩm đã sắp xếp một cách tham lam, dừng lại khi cái túi đầy và trả về kết quả:
Các thuật toán sắp xếp (sorting algorithm) tích hợp sẵn thường mất thời gian \(O(n \log n)\) và độ phức tạp không gian (space complexity) của chúng thường là \(O(\log n)\) hoặc \(O(n)\), tùy thuộc vào cách triển khai cụ thể của ngôn ngữ lập trình.
Bên cạnh việc sắp xếp, trong trường hợp xấu nhất, toàn bộ danh sách vật phẩm cần phải được duyệt qua, do đó độ phức tạp thời gian (time complexity) là \(O(n)\), trong đó \(n\) là số lượng vật phẩm.
Vì danh sách đối tượng Item được khởi tạo, độ phức tạp không gian là \(O(n)\).
Chứng minh tính đúng đắn¶
Chúng ta sử dụng chứng minh phản chứng (proof by contradiction). Giả sử vật phẩm \(x\) có giá trị đơn vị cao nhất và một thuật toán nào đó tạo ra một giá trị tối ưu là res, nhưng lời giải thu được không bao gồm vật phẩm \(x\).
Bây giờ, hãy bớt đi một đơn vị trọng lượng từ bất kỳ vật phẩm nào trong cái túi và thay thế nó bằng một đơn vị trọng lượng từ vật phẩm \(x\). Vì vật phẩm \(x\) có giá trị đơn vị cao nhất, nên tổng giá trị sau khi thay thế chắc chắn sẽ lớn hơn res. Điều này mâu thuẫn với giả định rằng res là tối ưu, từ đó chứng minh rằng mọi lời giải tối ưu đều phải bao gồm vật phẩm \(x\).
Chúng ta cũng có thể thiết lập mâu thuẫn tương tự đối với các vật phẩm khác trong lời giải. Tóm lại, các vật phẩm có giá trị đơn vị cao hơn luôn là lựa chọn tốt hơn, điều này chứng minh rằng chiến lược tham lam là hiệu quả.
Như thể hiện trong hình dưới đây, nếu chúng ta coi trọng lượng vật phẩm và giá trị đơn vị là trục hoành và trục tung của biểu đồ hai chiều, thì bài toán cái túi phân số có thể được nhìn nhận dưới dạng "tìm diện tích lớn nhất được bao quanh trong một khoảng giới hạn trên trục hoành". Sự tương đồng này giúp giải thích tính hiệu quả của chiến lược tham lam từ góc nhìn hình học.
