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
giao trinh bkhn
Trả lờiXóa