---
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

#include<bits/stdc++.h>
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:
* 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:**

#include <bits/stdc++.h>  
using namespace std;
int n;
pair<int, int> a[1005];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        // lưu first là thời gian kết thúc để khi ta sort thì thời gian kết thúc sẽ được sắp xếp
        cin >> a[i].second >> a[i].first;  
    sort(a + 1, a + 1 + n);
    int ans = 0;
    int time = 0;
    for (int i = 1; i <= n; ++i){
        if (a[i].second >= time){
            time = a[i].first; 
            ++ans;
        }    
    }
    cout << ans;
    return 0;
}

:::
## [Tasks and Deadlines](https://cses.fi/problemset/task/1630)
### Đề bài:
* Cho $n$ nhiệm vụ. Mỗi nhiệm vụ ta được cho thời gian để hoàn thành công việc và thời hạn để làm xong công việc ấy, bạn sẽ là người chọn thứ tự làm các công việc. Phần thưởng của bạn cho một nhiệm vụ là $d - f$ trong đó d là thời hạn và f là thời gian hoàn thành của bạn. Thời gian khi bắt đầu của bạn là 0 và bạn phải hoàn thành tất cả công việc được giao kể cả khi bạn bị trễ deadline. Phần thưởng tối đa của bạn là bao nhiêu nếu bạn hành động tối ưu?
#### Input:
* Dòng đầu tiên duy nhất là số $n$ ($1 \le n \le 2 * 10^5$)
* $n$ dòng tiếp theo gồm 2 số là $f$ (thời gian hoàn thành công việc) và $d$ (thời hạn hoàn thành công việc đó) ($1 \le f, d \le 10^6$)
#### Output:
* Một số duy nhất là số phần thưởng lớn nhất
#### Sample Input:

3
6 10
8 15
5 12

#### Sample Output:

2

#### Giải thích:

- Đầu tiên, ta làm công việc cuối cùng, thời gian thành $0 + 5 = 5$ và ta nhận được phần thưởng là $12 - 5 = 7$.
- Sau đó, ta làm công việc đầu tiên, thời gian thành $5 + 6 = 11$ và ta nhận được phần thưởng là $10 - 11 = -1$.
- Cuối cùng, ta làm công việc thứ hai, thời gian thành $11 + 8 = 19$ và ta nhận được phần thưởng là $19 - 15 = -4$.
- Do đó, phần thưởng cuối cùng ta nhân được là: $7 + (-1) + (-4) = 2$.
### Lời giải:
:::spoiler **Ý tưởng:**
* Ta có thể nhìn thấy rằng có thể làm các công việc với thời gian làm việc từ ít nhất đến nhiều nhất. Và đó chính là thuật toán tham lam chính xác. Ta thấy rằng thời hạn của các công việc không thay đổi, nhưng nếu ta làm những công việc có thời gian hoàn thành nhỏ hơn trước, ta có thể giảm thiểu thời gian vượt thời hạn của các nhiệm vụ sau một cách tối đa, vì thế thuật toán tham lam này hoạt động.
:::
:::spoiler **Code mẫu:**

#include <bits/stdc++.h>  
using namespace std;
int n;
pair<int, int> a[200005];
int main()
{
    cin>>n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].first >> a[i].second;
    }
    sort(a + 1,a + 1 + n);
    long long cur = 0, ans = 0;
    for (int i = 1; i <= n; ++i){
       cur += a[i].first;
       ans += (a[i].second - cur);
    }
    cout<<ans;
    return 0;
}

:::
## [Stick Lengths](https://cses.fi/problemset/task/1074/)
### Đề bài:
* Bạn được cho độ dài của $n$ cái que. Nhiệm vụ của bạn là sửa đổi các que sao cho mỗi que có cùng chiều dài. Bạn có thể kéo dài và rút ngắn từng thanh. Cả hai thao tác đều tốn $x$ trong đó $x$ là chênh lệch giữa độ dài mới và độ dài ban đầu.
* Tổng chi phí tối thiểu là bao nhiêu?
#### Input:
* Dòng đầu tiên gồm một số $n$: số que. ($1 \le n \le 2 * 10^5$)
* Dòng thứ hai gồm $n$ số nguyên là độ dài $p$ của que ($1 \le p \le 10^9$)
#### Output:
* Ghi một số duy nhất là chi phí tối thiểu.
#### Sample Input:

5
2 3 1 5 2

#### Sample Output:

5

#### Giải thích:

### Lời giải:
:::spoiler **Ý tưởng:**
* Gọi $a[x]$: độ dài của que $x$.
* Để giải quyết bài toán này, ta trước hết cần sắp xếp lại độ dài của que. Khi này, ta thấy rằng bên trái của một que $x$ sẽ là các que có độ dài nhỏ hơn $a[x]$, để tính được chi phí làm các que này có độ dài bằng que $x$, ta cần lấy tổng nếu như các que đó có độ dài bằng $a[x]$ trừ đi tổng hiện tại => Công thức: $a[x] * (x - 1)$ trừ đi tổng từ $a[1] -> a[x - 1]$.
* Đồng thời, ta cũng cần làm tương tự với bên phải của $x$, vì bên phải là những phần tử lớn hơn $a[x]$ nên để tính được chi phí làm các que này có độ dài bằng que $x$, ta cần lấy tổng hiện tại trừ đi tổng nếu như các que đó có độ dài bằng $a[x]$
$\Rightarrow$ **Công thức:** tổng từ $a[x + 1] -> 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:**

#include <bits/stdc++.h>  
using namespace std;
int n , a[200005];
int main()
{
    cin >> n;
    long long prev = 0, after = 0;
    for (int i = 1; i <= n; i++)
      cin>>a[i];
    sort(a + 1, a + n + 1);
    for (int i = 2; i <= n; i++){
         after += (a[i]-a[1]);
    }
    long long ans = after + prev;
    for (long long i = 2; i <= n; i++){
      prev += ((i - 1) * (a[i] - a[i - 1]));
      after -= ((a[i] - a[i-1]) * (n - i + 1));
      ans = min(ans, after + prev);
    }
    cout<<ans;
    return 0;
}

:::
# Khái niệm Adhoc
## Khái niệm
- Các bài toán đặc biệt là các bài toán không thể phân loại vào bất cứ lớp bài toán nào, và các phương pháp giải quyết bài toán được coi là độc đáo. Các bài toán này có thể được phân loại thành hai dạng: đơn giản và bài toán mô phỏng (bài toán có một số quy tắc mô phỏng câu trả lời).

## Link trang web tham khảo thêm
### [Adhoc và tips làm bài](https://usaco.guide/bronze/ad-hoc)
### [What are Ad Hoc Problems in Competitive Programming?](https://www.geeksforgeeks.org/what-are-ad-hoc-problems-in-competitive-programming/)

# Bài tập vận dụng
## Bài 1: [CSES - Towers](https://cses.fi/problemset/task/1073)
### Đề bài:
* Bạn được cấp $n$ khối theo một thứ tự nhất định và nhiệm vụ của bạn là xây dựng các tòa tháp bằng cách sử dụng chúng. Khi hai khối lập phương chồng lên nhau thì khối trên phải nhỏ hơn khối dưới.
* Bạn phải xử lý các hình khối theo thứ tự nhất định. Bạn luôn có thể đặt khối lập phương lên trên một tòa tháp hiện có hoặc bắt đầu một tòa tháp mới. Số lượng tháp tối thiểu có thể là bao nhiêu?
#### Input:
* Dòng đầu tiên gồm một số $n$: số khối. ($1 \le n \le 2 * 10^5$)
* Dòng tiếp theo gồm $n$ số là kích thước k của khối. ($1 \le k \le 10^9$)
#### Output:
* Ghi một số duy nhất là chi phí tối thiểu.
#### Sample Input:

5
3 8 2 1 5

#### Sample Output:

2

## Bài 2: [Codeforces - The Party and Sweet](https://codeforces.com/problemset/problem/1158/A)
### Đề bài:
* Cho $n$ chàng trai và $m$ cô gái. Mỗi chàng trai quyết định tặng một số kẹo cho từng cô gái. Ta được cho mảng b gồm n phần tử với b[i] là số kẹo ít nhất mà chàng trai thứ i tặng cho 1 cô gái bất kì và mảng g gồm m phần tử với g[j] là số kẹo nhiều nhất mà cô gái thứ j nhận từ 1 chàng trai bất kì. Hãy tính tổng số kẹo ít nhất mà các chàng trai cần chuẩn bị để số kẹo thỏa các điều kiện của mảng b và g. Nếu không thể chuẩn bị kẹo theo yêu cầu thì đưa ra đáp án là $-1$.
#### Input:
* Dòng đầu tiên gồm hai số nguyên n và m - số lượng chàng trai và cô gái. ($2 \le n, m \le 10^5$)
* Dòng thứ hai là mảng b gồm n phần tử ($0 \le b[i] \le 10^8$)
* Dòng thứ ba là mảng g gồm m phần tử ($0 \le g[i] \le 10^8$)
#### Output:
* Ghi tổng số kẹo ít nhất mà các chàng trai cần chuẩn bị hoặc báo là không thực hiện được ghi ra -1.
#### Sample Input:

3 2
1 2 1
3 4

#### Sample Output:

12

* Giải thích: Tổng số kẹo tối thiểu mà các chàng trai có thể đưa ra là $12$. Khi đó, chàng trai đầu tiên sẽ tặng các cô gái $1$ và $4$ viên kẹo, chàng trai thứ hai tặng $3$ và $2$ viên kẹo và chàng trai thứ ba tặng $1$ và $1$ viên kẹo cho cô gái thứ nhất và thứ hai. Dễ dàng nhận thấy mọi điều kiện đều được thỏa mãn và tổng số kẹo là 12.
## Bài 3: [CSES - Stick Divisions](https://cses.fi/problemset/task/1161)
### Đề bài:
* Bạn có một cây gậy có chiều dài $x$ và bạn muốn chia nó thành $n$ cây gậy có độ dài cho trước, có tổng chiều dài là $x$.
* Trong mỗi lần di chuyển, bạn có thể lấy bất kỳ cây gậy nào và chia nó thành hai cây gậy. Chi phí của hoạt động như vậy là chiều dài của thanh ban đầu.
* Chi phí tối thiểu cần thiết để tạo ra những chiếc gậy là bao nhiêu?
#### Input:
* Dòng đầu tiên gồm hai số nguyên $x$ và $n$: độ dài của cây gậy và số cây gậy được chia ra từ cây gậy ban đầu. ($1 \le n \le 2 * 10^5$) ($1 \le x \le 10^9$)
* Dòng thứ hai chứa $n$ số nguyên là độ dài của $n$ cây gậy được chia ra. (tổng độ dài của $n$ cây gậy này là $x$)
#### Output:
* Ghi một số duy nhất là chi phí tối thiểu cần thiết để tạo ra những chiếc gậy.
#### Sample Input:

8 3
2 3 3

#### Sample Output:

13

* Giải thích: Đầu tiên bạn chia que dài 8 thành que dài 3 và 5 (giá 8). Sau đó, bạn chia que có chiều dài 5 thành que có chiều dài 2 và 3 (giá 5). Tổng chi phí là 8 + 5 = 13.
# Nguồn tham khảo
- [Thuật toán tham lam - Greedy Algorithm](https://viblo.asia/p/thuat-toan-tham-lam-greedy-algorithm-XQZGxozlvwA)
- [Competitive Programming's Handbook](https://usaco.guide/CPH.pdf)