Khác biệt giữa bản sửa đổi của “Bài toán xếp ba lô”

'''Bài toán xếp ba lô''' (một số sách ghi là '''bài toán cái túi''') là một bài toán [[tối ưu hóa tổ hợp]]. Bài toán được đặt tên từ vấn đề chọn những gì quan trọng có thể nhét vừa vào trong một cái túi (với giới hạn khối lượng) để mang theo trong một chuyến đi. Các bài toán tương tự thường xuất hiện trong kinh doanh, [[toán học tổ hợp|toán tổ hợp]], [[lý thuyết độ phức tạp tính toán]], [[mật mã học]] và [[toán học ứng dụng|toán ứng dụng]].

Bài toán xếp ba lô thường được giải bằng [[quy hoạch động]], tuy chưa có một [[thuật toán thời gian đa thức]] cho bài toán tổng quát. Cả bài xếp ba lô tổng quát và bài toán tổng con đều là các bài [[NP-khó]], và điều này dẫn đến các cố gắng sử dụng tổng con làm cơ sở cho các hệ thống [[mật mã hóa khóa công khai]], chẳng hạn [[Merkle-Hellman]]. Các cố gắng này thường dùng [[nhóm (toánđại họcsố)|nhóm]] thay vì các số nguyên. Merkle-Hellman và một số thuật toán tương tự khác đã bị phá, do các bài toán tổng con cụ thể mà họ tạo ra thực ra lại giải được bằng các thuật toán thời gian đa thức.