Báo Cáo Phương pháp xấp xỉ giải bài toán cái túi

Phân tích, thiết kế và đánh giá thuật toán là một trong những nhân tố mấu chốt xác định được hiệu năng hệ thống khi giải quyết bài toán tin học đặt ra. Có nhiều bài toán lời giải (thuật toán) được đưa ra chỉ tốt ở một mức độ chấp nhận được. Việc tính toán cho phép chấp nhận một sai số nào đó. Vì vậy, thời gian gần đây, phương pháp xấp xỉ được quan tâm và phát triển trong một số ứng dụng. Có rất nhiều bài toán mà ta có thể giải bằng kĩ thuật, phương pháp này. Trong đó phải đề cập đến bài toán cái túi (Knapsack), hay còn gọi là bài toán xếp ba lô- đây là một bài toán tối ưu hoá 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.
Liên quan đến việc giải bài toán này chúng ta có rất nhiều phương án khác nhau như: Phương pháp quy hoạch động, phương pháp tham lam, phương pháp nhánh cận .
Ở mỗi phương pháp đều có những ưu và nhược điểm riêng. Tuy nhiên nói chung chúng ta chỉ đạt được một phương án tốt chứ chưa hẳn là tối ưu.