Bạn đọc bản dịch này bằng các ngôn ngữ khác: English
Vấn đề ba lô, hay còn gọi là vấn đề túi rủ, là một vấn đề trong tối ưu hóa tổ hợp: Cho một tập hợp các mặt hàng, mỗi mặt hàng có trọng lượng và giá trị, hãy xác định số lượng của mỗi mặt hàng để bao gồm trong một bộ sưu tập sao cho tổng trọng lượng nhỏ hơn hoặc bằng một ngưỡng cho trước và tổng giá trị là lớn nhất có thể.
Tên của vấn đề được lấy từ tình huống mà ai đó bị ràng buộc bởi một chiếc ba lô có kích thước cố định và phải điền đầy nó với những mặt hàng có giá trị nhất.
Ví dụ về vấn đề túi rủ một chiều (hạn chế): cần chọn những hộp nào để tối đa hóa số tiền trong khi vẫn giữ trọng lượng tổng thể dưới hoặc bằng 15 kg?
Vấn đề phổ biến nhất được giải quyết là vấn đề túi rủ 0/1, giới hạn số lượng xi của mỗi loại mặt hàng là không hoặc một.
Cho một tập hợp các mặt hàng có số thứ tự từ 1 đến n, mỗi mặt hàng có trọng lượng wi và giá trị vi, cùng với một trọng lượng tối đa W,
tối đa
điều kiện 
Ở đây, xi đại diện cho số lượng của mỗi mặt hàng để bao gồm trong ba lô. Một cách không chính thức, vấn đề là tối đa hóa tổng giá trị của các mặt hàng trong ba lô sao cho tổng trọng lượng nhỏ hơn hoặc bằng khả năng chứa của ba lô.
Vấn đề túi rủ có giới hạn (BKP) loại bỏ ràng buộc là chỉ có một của mỗi mặt hàng, nhưng hạn chế số lượng xi bản sao của mỗi loại mặt hàng thành một giá trị số nguyên không âm tối đa c:
tối đa
điều kiện
Vấn đề túi rủ không giới hạn (UKP) không đặt ra hạn chế trên số lượng bản sao của mỗi loại mặt hàng và có thể được sắp xếp như trên ngoại trừ việc rằng ràng buộc duy nhất đối với xi là nó phải là số nguyên không âm.
tối đa
điều kiện
