Thuật toán nhánh và cận áp dụng cho BT Cái túi

I.Đặt vấn đề

1.Bài toán thực tế

Một nhà thám hiểm cần đem theo 1 cái túi có trọng lượng không quá b,có n đồ vật mang theo.Đồ vật thứ j có trọng lượng là aj và có giá trị sử dụng  là cj(j=1,2,…n)

Yêu cầu :

Hỏi rằng  nhà thám hiểm cần mang theo các đồ vật nào  để cho tổng giá trị sử dụng  các đồ vật đem theo là lớn nhất?

2.Giải quyết bài toán

- Phương pháp vét cạn

- Phương pháp quay lui

-Một số phương pháp khác

3.Nhược điểm của các phương pháp trên là phải xét cả những phương án không khả thi, gây bùng nổ khi dữ liệu vào n quá lớn

Download Slide và Code mẫu