Đặc điểm: Đây là bài toán Cái túi (Knapsack) dạng 0/1.
Ràng buộc đáng chú ý:
Số lượng vật nhỏ ().
Trọng lượng túi và trọng lượng vật rất lớn (lên đến ).
Giá trị vật khá nhỏ ().
Vấn đề: Nếu dùng phương pháp Quy hoạch động (QHĐ) truyền thống với trạng thái là trọng lượng (giá trị lớn nhất với trọng lượng ), mảng sẽ không thể chứa nổi chỉ số .
Giải pháp: Thay vì tính giá trị lớn nhất theo trọng lượng, ta sẽ tính trọng lượng nhỏ nhất để đạt được một giá trị nhất định.
2. Ý tưởng thuật toán
Tổng giá trị tối đa tất cả các vật có thể đạt được là: .
Gọi là trọng lượng tổng nhỏ nhất để đạt được tổng giá trị đúng bằng .
Mục tiêu: Tìm giá trị lớn nhất sao cho .
3. Các bước thực hiện
Khởi tạo:
Tạo mảng có kích thước .
Đặt (trọng lượng để có giá trị 0 là bằng 0).
Tất cả các vị trí còn lại đặt bằng một giá trị vô cùng lớn ().
Duyệt các vật: Với mỗi vật thứ có trọng lượng và giá trị :
Duyệt ngược biến từ xuống (để tránh dùng một vật nhiều lần):
Cập nhật: .
Tìm kết quả:
Duyệt từ ngược về .
Giá trị đầu tiên thỏa mãn chính là đáp án cần tìm.
4. Lưu ý khi triển khai
Kiểu dữ liệu: Trọng lượng và có thể lên đến , do đó mảng và các biến liên quan đến trọng lượng phải dùng kiểu số nguyên 64-bit (ví dụ: long long trong C++ hoặc số nguyên mặc định trong Python).
Giá trị vô cùng: Chọn một hằng số đủ lớn (lớn hơn tổng tất cả có thể có, ví dụ hoặc hơn).
Tối ưu: Chỉ cần duyệt đến tổng giá trị thực tế của các vật đang có thay vì luôn duyệt đến .
