Mục lục

[URL="/#_Toc310210418"]Giới thiệu : 3

[URL="/#_Toc310210419"]Chương I : Bài toán cái túi 4

[URL="/#_Toc310210420"]1.1 Giới thiệu. 4

[URL="/#_Toc310210421"]1.2 Bài toán cái túi dạng 0-1. 4

[URL="/#_Toc310210422"]1.3 Bài toán cái túi dạng phân số. 5

[URL="/#_Toc310210423"]Chương 2: Giải bài toán cái túi bằng thuật toán trực tiếp (Brute-force) 5

[URL="/#_Toc310210424"]Chương 3: Giải bài toán cái túi bằng thuật toán tham lam 5

[URL="/#_Toc310210425"]3.1 Greedy 1. 5

[URL="/#_Toc310210426"]3.2 Greedy 2. 5

[URL="/#_Toc310210427"]3.3 Greedy 3. 5

[URL="/#_Toc310210428"]3.4 Greedy 4. 5

[URL="/#_Toc310210429"]3.5 Thực hiện bài toán cái túi theo Greedy 3 bằng C++. 6

[URL="/#_Toc310210430"]Chương IV: Giải bài toán cái túi bằng thuật toán quy hoạch động. 7

[URL="/#_Toc310210431"]4.1 Mô tả: 7

[URL="/#_Toc310210432"]4.2 Nhận xét: 8

[URL="/#_Toc310210433"]Tài liệu tham khảo chính: 9

[FONT="]

Giới thiệu :

Báo cáo này sẽ trình bày về các thuật toán giải quyết bài toán cái túi. Trong đó có sử dụng 2 giải thuật là: giải thuật tham lam (Greedy) và Quy hoạch động (Dynamic progaming). Từ đó đưa ra các đánh giá về độ phức tạp của thuật toán và lựa chọn phương án tối ưu.

Xin chân thành cám ơn thầy Nguyễn Đức Nghĩa đã giúp đỡ em thực hiện bài toán này

Hà Nội tháng 12 năm 2011 [FONT="]