TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
Viện Công nghệ Thông tin và Truyền thông
BÀI TẬP LỚN MÔN HỌC
THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁN
Đề tài:
BÀI TOÁN CÁI TÚI
Học viên thực hiện:
1. Đào Duy Thành. SHHV:20082364
Mã lớp: 29106
Giáo viên hướng dẫn: PGS Nguyễn Đức Nghĩa
HÀ NỘI – 2011
1
Mục lục
Mục lục 2
Giới thiệu : 3
Chương I : Bài toán cái túi 4
1.1Giới thiệu 4
1.2Bài toán cái túi dạng 0-1 4
1.3Bài toán cái túi dạng phân số 5
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
Chương 3: Giải bài toán cái túi bằng thuật toán tham lam 5
3.1 Greedy 1 5
3.2 Greedy 2 5
3.3 Greedy 3 5
3.4 Greedy 4 5
3.5 Thực hiện bài toán cái túi theo Greedy 3 bằng C++ 6
Chương IV: Giải bài toán cái túi bằng thuật toán quy hoạch động 7
4.1 Mô tả: 7
4.2 Nhận xét: 8
Tài liệu tham Khảo chính: 9
2

Sao cho với
Bài cái túi không bị chặn Không có một hạn chế nào về số lượng đồ vật mỗi loại.
Một trường hợp đặc biệt của bài toán này nhận được nhiều quan tâm, đó là bài toán với các tính
chất:
•
•
•
là một bài toán quyết định
là một bài toán 0/1
với mỗi đồ vật, chi phí bằng giá trị: C = V
4
Trường hợp đặc biệt này được gọi là bài toán tổng các tập con (subset sum problem). Với
một số lý do, trong ngành mật mã học, người ta thường dùng cụm từ "bài toán cái túi Khi thực ra
đang có ý nói về "bài toán tổng con".
Bài toán cái túi 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 cái túitổ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 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.
Phiên bản bài toán quyết định của bài toán cái túi được mô tả ở trên là NP-đầy đủ và trong
thực tế là một trong 21 bài toán NP-đầy đủ của Karp.
1.3 Bài toán cái túi dạng phân số
Với mỗi loại, có thể chọn một phần của nó (ví dụ: 1Kg bơ có thể được cắt ra thành nhiều
phần để bỏ vào ba lô)
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)
Phương pháp này duyệt tất cả Khả năng chất đồ vào túi, tìm cách chất có tổng giá trị lớn
nhất trong số các cách chất co tổng trọng lượng các đồ vật Không quá dung lượng của túi
Tuy nhiên, phương pháp này ít được sử dụng do có độ phức tạp O (n2)
Chương 3: Giải bài toán cái túi bằng thuật toán tham lam

•
•
•
•
Độ phức tạp:
swap (x,y) được dùng để đổi chỗ biến x và y Khi sắp xếp
nhap() dùng để nhập dữ liệu từ bàn phím
sapxep() được dùng để sắp xếp lại mảng theo thứ tự giảm dần của tỉ lệ v[i]/w[i] , tức
là tỉ lệ giảm dần của giá trị trên Khối lượng mỗi đồ vật
thamlam() lần lượt trọn các đồ vật đã được sắp xếp theo thứ tự giảm dần của giá trị
trên Khối lượng, biến Kỉ lục ghi nhận Kết quả tốt nhất Khi thực hiện
•
•
Nếu sử dụng sắp xếp đơn giản (chèn, nổi bọt…) thì độ phức tạp của cả bài toán là O(n2)
Nếu sử dụng quicK sort hoặc merge sort thì độ phức tạp là O(nlogn) tốt hơn so với giải trực
tiếp
Giao diện nhập số liêu
6
Kết quả thu được
Chương IV: Giải bài toán cái túi bằng thuật toán quy hoạch động.
4.1 Mô tả:
•
Với mỗi và , xét bài toán . Tính là tổng
giá trị lớn nhất của các đồ vật được chọn trong số K đồ vật đầu tiên và có tổng trọng
lượng Không quá S.
•
Có tất cả bài toán. Bài toán cần giải là
•
•
Giá trị tối ưu cần tìm là