- 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 using namespace std; // Định nghĩa cấu trúc đối tượng nếu cần // Hàm so sánh nếu cần // Hàm thực hiện thuật toán tham lam void solve[/* Tham số đầu vào nếu cần */] { // Bước 1: Chuẩn bị dữ liệu nếu cần // Bước 2: Sắp xếp dữ liệu nếu cần // Bước 3: Thực hiện thuật toán tham lam // Bước 4: In kết quả nếu cần } int main[] { ios_base::sync_with_stdio[false]; cin.tie[NULL]; // Bước 1: Nhập dữ liệu nếu cần // Bước 2: Gọi hàm thực hiện thuật toán tham lam // Bước 3: In kết quả nếu cần return 0; } ``` ## Đặc điểm của tham lam - Gần gũi, dễ tiếp cận. - Dễ dàng hơn trong quản lí cũng như tính toàn tài nguyên của bài toán [time and memory]. - Cần phải xác định, tính toán, chứng minh tính đúng đắn của thuật toán. Chứng minh tại sao những lựa chọn của thuật toán là những lựa chọn tối ưu. # Bài tập ví dụ ## Bài toán sự kiện ### Đề bài: * Cho $N$ sự kiện với thời gian bắt đầu và kết thúc. Hãy tìm cách chọn nhiều sự kiện nhất sao cho các sự kiện đó không trùng nhau [sự kiện bắt đầu ngay sau khi sự kiện kia kết thúc cũng là không trùng nhau]. #### Input: * Dòng đầu tiên gồm số $N$ [$1 \le N \le 1000$] * $N$ dòng tiếp theo, mỗi dòng là thời gian bắt đầu và kết thúc của sự kiện [mọi thời gian đều nhỏ hơn $10^9$] #### Output: * Một số duy nhất là số sự kiện không trùng nhau nhiều nhất #### Sample Input: ``` 4 1 3 2 5 3 9 6 8 ``` #### Sample Output: ``` 2 ``` * Giải thích: Ta chọn sự kiện đầu tiên và cuối cùng ### Lời giải: :::spoiler **Ý tưởng:** * Ý tưởng thứ ba là luôn chọn sự kiện kết thúc sớm nhất trong các sự kiện khả thi. Thuật toán này chọn các sự kiện sau: ![image][//hackmd.io/_uploads/HyYGtnI_6.png] * Thuật toán này luôn tạo ra một giải pháp tối ưu. Lý do cho điều này là việc chọn một sự kiện kết thúc sớm nhất thì ta sẽ luôn có nhiều khả năng nhất để tìm được sự kiện tiếp theo, vì thế thuật toán sẽ hoạt động chính xác. * Một cách để lập luận rằng thuật toán hoạt động là xem xét điều gì sẽ xảy ra nếu chúng ta chọn một sự kiện kết thúc muộn hơn sự kiện kết thúc sớm nhất. Bây giờ, chúng ta sẽ có số lựa chọn bằng nhau để chọn sự kiện tiếp theo. Do đó, việc chọn một sự kiện kết thúc muộn hơn không bao giờ có thể mang lại giải pháp tốt hơn, và thuật toán tham lam là chính xác. ::: :::spoiler **Code mẫu:** ```cpp=

include using namespace std; int n; pair a[1005]; int main[] { cin >> n; for [int i = 1; i > a[i].second >> a[i].first; sort[a + 1, a + 1 + n]; int ans = 0; int time = 0; for [int i = 1; i = time]{ time = a[i].first; ++ans; } } cout >n; for [int i = 1; i > a[i].first >> a[i].second; } sort[a + 1,a + 1 + n]; long long cur = 0, ans = 0; for [int i = 1; i a[n]$ trừ đi $a[x] * [n - x]$. * Chi phí nhỏ nhất sẽ là min của tổng trái và phải này của tất cả các phần tử. * Để tính tổng các đoạn của mảng, ta có thể sử dụng mảng cộng dồn hoặc duy trì hai biến. ::: :::spoiler **Code mẫu:** ```cpp=

include using namespace std; int n , a[200005]; int main[] { cin >> n; long long prev = 0, after = 0; for [int i = 1; i >a[i]; sort[a + 1, a + n + 1]; for [int i = 2; i