Nội dung chính của bài viết trình bày Thuật toán tham lam là tìm tối ưu địa phương ở mỗi bước đi với hy vọng tìm được tối ưu toàn cục. Dĩ nhiên thuật toán tham lam không đảm bảo được tối ưu địa phương sẽ cho ta lời giải tối ưu toàn cục. Mời các bạn tham khảo! | THUẬT TOÁN THAM LAM TRONG XÂY DỰNG CẤU HÌNH TỔ HỢP Trần Minh Hiền THPT Chuyên Quang Trung Bình Phước Thuật toán tham lam là tìm tối ưu địa phương ở mỗi bước đi với hy vọng tìm được tối ưu toàn cục. Dĩ nhiên thuật toán tham lam không đảm bảo được tối ưu địa phương sẽ cho ta lời giải tối ưu toàn cục. Nhưng trong nhiều bài toán việc này sẽ xảy ra. Ví dụ quot Cho trước một tập hợp S các đồng xu. Khi đó cần lấy ít nhất bao nhiêu đồng xu trong S để được tổng số tiền M cho trước. Khi S D f1 5 10 25g chúng ta có thể áp dụng thuật toán tham lam để xây dựng phương án tối ưu như sau Thêm đồng xu x lớn nhất trong S sao cho x M Áp dụng lại thuật toán cho M x. Ví dụ với M D 91 đầu tiên ta chọn 25 trong S sau đó lại tiếp tục áp dụng thuật toán cho 91 25 D 66. Khi đó ta lại tiếp tục chọn số tục áp dụng thuật toán cho 66 25 D 41 ta chọn số 25. Lại áp dụng thuật toán cho 41 25 D 16 ta sẽ chọn số 10. Lại tiếp tục áp dụng thuật toán cho 16 10 D 6 thì ta chọn số 5. Và cuối cùng áp dụng thuật toán cho 6 5 D 1 ta chọn số 1. Từ đó tập hợp tối ưu là f25 25 25 10 5 1g. Tức là với tập S D f1 5 10 25g thuật toán tham lam cho ta phương án tối ưu. Tuy nhiên thuật toán tối ưu không phải lúc nào cũng cho ta phương án tối ưu. Ví dụ với S D f1 3 4g và M D 6 thuật toán tham lam cho ta tập f1 1 4g tuy nhiên phương án tối ưu là f3 3g. quot Dưới đây là một số bài toán minh họa. Câu 1 BMO 1998 . Một đại lý vé tàu hỏa phân phối vé tàu hỏa cho 200 đại lý. Trong một ngày đặc biệt có tất cả 3800 người ở 200 đại lý đến mua vé mỗi người được mua một vé. 1. Chứng minh rằng có ít nhất 6 đại lý có cùng số người đến mua vé trong ngày hôm đó. 2. Ý trên không còn đúng nếu thay 6 bởi số 7. Lời giải. 1. Gọi s1 s2 s200 là số người đến đại lý thứ nhất đại lý thứ hai đại lý thứ 200 mua vé tàu hỏa trong ngày đó. Không mất tính tổng quát ta có thể giả sử s1 s2 s200 . Đặt S D s1 C s2 C C s200 thì S D 3800. Bây giờ ta sẽ tìm hiểu S nhỏ nhất bao nhiêu khi điều kiện bài toán không thỏa tức không tồn tại dãy si si C1
