Tổng quan
Bài toán Knapsack 0/1 hỏi tập con vật phẩm nào, mỗi vật có một khối lượng và một giá trị, vừa với giới hạn khối lượng mà tổng giá trị lớn nhất. Chữ 0/1 nghĩa là mỗi vật hoặc lấy nguyên hoặc bỏ lại — không có phần lẻ.
Chính ràng buộc đó khiến bài toán khó. Phiên bản chia nhỏ được thì giải bằng một quy tắc tham lam — sắp theo giá trị trên một đơn vị khối lượng rồi nhét vào — nhưng tham lam thất bại ở đây, và thất bại theo cách đáng xem: một vật nặng, giá trị cao có thể thắng vài vật nhẹ có tỉ lệ tốt hơn. Mỗi ô của bảng quy hoạch động trả lời đúng một câu hỏi về một vật: bỏ qua, hay lấy nó và tiêu tốn khối lượng của nó?
Knapsack 0/1 hoạt động thế nào?
- Dựng bảng trong đó hàng i xét i vật phẩm đầu tiên và cột w xét ngân sách sức chứa từ 0 tới W.
- Hàng 0 toàn số 0: không có vật nào thì mọi sức chứa đều cho giá trị bằng 0.
- Với mỗi ô, trước hết xét việc bỏ qua vật i — đáp án chính là ô ngay phía trên.
- Nếu vật i vừa với sức chứa hiện tại, xét thêm phương án lấy nó: giá trị của nó cộng kết quả tốt nhất cho phần sức chứa còn lại lấy từ hàng trước.
- Lưu giá trị lớn hơn trong hai phương án. Ô cuối chứa giá trị lớn nhất; lần ngược lên trên, so mỗi ô với ô phía trên nó để biết những vật nào đã được chọn.
Khi nào nên dùng?
- Phân bổ ngân sách: chọn tập dự án cho tổng lợi ích cao nhất dưới một mức chi cố định.
- Xếp hàng hóa và container, khi các kiện không chia nhỏ được và sức chứa bị chặn cứng.
- Xếp lịch tài nguyên dưới trần CPU, bộ nhớ hay băng thông, với mỗi tác vụ là lựa chọn được-ăn-cả-ngã-về-không.
- Bộ khung cho cả một họ bài toán: knapsack không giới hạn, tổng tập con, chia mảng thành hai phần bằng nhau và đổi tiền đều là biến thể của cái bảng này.
Phân tích độ phức tạp
Thời gian và bộ nhớ đều là O(n·W), với n là số vật phẩm và W là sức chứa. Trông có vẻ đa thức nhưng thực ra không phải, theo nghĩa chặt: W là một giá trị số, và viết nó ra chỉ tốn log W bit, nên bảng tăng theo hàm mũ so với kích thước biểu diễn đầu vào. Đó là ý nghĩa của cụm 'giả đa thức', và là lý do knapsack 0/1 thuộc lớp NP-khó dù có lời giải bằng cách điền bảng. Bộ nhớ giảm được về O(W) với một hàng duy nhất, bằng cách duyệt sức chứa theo chiều giảm để mỗi vật chỉ dùng nhiều nhất một lần.
Câu hỏi thường gặp
Vì sao quy tắc tham lam theo giá trị trên khối lượng lại thất bại?
Vì lấy vật có tỉ lệ tốt nhất có thể để lại phần sức chứa thừa quá nhỏ để dùng được. Với sức chứa 10 và các vật (6kg, 30đ) cùng hai vật (5kg, 20đ), tỉ lệ tốt nhất là vật 6kg với 5đ/kg — lấy nó thì 4kg bị bỏ phí, được 30đ. Lấy cả hai vật 5kg được 40đ. Tham lam không thấy được đánh đổi đó vì nó không bao giờ xét lại.
Vì sao bản tối ưu một hàng lại duyệt sức chứa theo chiều ngược?
Duyệt xuôi sẽ đọc phải một ô đã cập nhật cho chính vật hiện tại, tương đương lấy vật đó hai lần — đó chính là bài knapsack không giới hạn. Duyệt theo chiều giảm đảm bảo mọi giá trị bạn đọc vẫn thuộc hàng trước.
Nếu sức chứa hoặc khối lượng không phải số nguyên thì sao?
Bảng được đánh chỉ số theo sức chứa, nên cần các bước rời rạc. Quy về một độ chính xác cố định — dùng gam thay vì kilôgam — thì chạy được nhưng nhân W lên và do đó nhân cả thời gian chạy. Khi cần độ chính xác cao, các lược đồ xấp xỉ hoặc nhánh-cận sẽ thay cho cái bảng.