Các thuật toán tham lam chia và trị năm 2024
- title Tham lam (Greedy) - Tham lam (Greedy) === - ###### ✍️ Author: 2School Guideline ###### 📋 Content: [TOC] - # Lời nói đầu - Bây giờ mẹ bạn cho bạn $2$ tờ tiền mệnh giá $100.000 đ$ và $200.000 đ$ và bạn chỉ được chọn $1$. Và đương nhiên mình sẽ chọn tờ $200.000 đ$ vì nó giá trị hơn mặc dù số lượng và kích thước của $2$ tờ đều như nhau. **Vậy những vấn đề được đặt ra ở trên sẽ được giải quyết một cách tối ưu nhất qua phương pháp nào?** **Các bạn hãy "tham lam" một chút và cùng chúng mình xem qua bài viết dưới đây để tìm hiểu rõ hơn nhé** # Tham lam ## Khái niệm - **Thuật toán tham lam (Greedy Algorithm)** là một phương pháp giải quyết vấn đề trong lĩnh vực khoa học máy tính và toán học. - Đặc điểm chính của thuật toán tham lam là nó tập trung vào việc đưa ra quyết định tại mỗi bước bằng cách chọn phương án tốt nhất tại thời điểm đó mà không xem xét các ảnh hưởng tương lai. ## Ý tưởng - Ý tưởng cơ bản của thuật toán tham lam là tại mỗi bước quyết định, chọn ra lựa chọn tốt nhất tại thời điểm đó dựa trên một tiêu chí nào đó mà không quay lại xem xét các lựa chọn đã được đưa ra trước đó. Thuật toán này tập trung vào việc đưa ra quyết định **"tốt nhất hiện tại"** mà không cần biết đến tương lai. - **Cách hoạt động của thuật Toán Tham Lam:** - **Xác Định Cấu Trúc Vấn Đề:** Phải có một cấu trúc rõ ràng của vấn đề, và mỗi bước lựa chọn không được ảnh hưởng bởi các bước quyết định trước đó. - **Xác Định Tiêu Chí Lựa Chọn:** Chọn một tiêu chí đánh giá sự tốt xấu của mỗi lựa chọn tại mỗi bước. Điều này có thể là giá trị, trọng lượng, tỉ lệ lợi ích/trọng lượng, và nhiều tiêu chí khác. - **Sắp Xếp Lựa Chọn:** Sắp xếp tất cả các lựa chọn theo tiêu chí đã chọn. Điều này giúp thuật toán chọn lựa nhanh chóng lựa chọn tốt nhất. - **Lựa Chọn Tham Lam:** Chọn ra lựa chọn tốt nhất tại thời điểm đó và thực hiện quyết định. Không quay lại xem xét lựa chọn đã được đưa ra trước đó. - **Lặp Lại Quy Trình:** Lặp lại quy trình trên cho đến khi đạt được giải pháp hoặc không thể thực hiện thêm bước nào nữa. ## Lựa chọn tối ưu là gì? - $1$ lựa chọn được coi là tối ưu nếu nó luôn là **tốt nhất** trong mọi trường hợp sau đó. - Tại $1$ thời điểm, nếu ta tìm được **lựa chọn tối ưu**, ta sẽ chỉ cần xem xét và lựa chọn nó $1$ lần duy nhất. Sau đó, ta có thể tiếp tục các vấn đề tiếp theo mà **không cần xem xét lại**. - **Ví dụ:** Hãy tìm số tự nhiên lớn nhất có $3$ chữ số. **Thứ tự xem xét:** ***hàng trăm* -> *hàng chục* -> *hàng đơn vị*.** > [] ## Cấu trúc của thuật toán tham lam ```cpp= include
|