# Chuyên đề: Tham lam
**Nó là gì?** Các thuật ngữ liên quan?
- Bài tóan tối ưu: Bài toán bao gồm nhiều bước, tại mỗi bước ta có một số lựa chọn khác nhau. Mỗi lựa chọn có thể đem lại lợi ích, hay mất mát, được biểu diễn dưới dạng các con số. Chiến thuật lựa chọn sao cho đạt *tổng lợi nhuận* **lớn nhất** chính là mục tiêu của *bài toán tối ưu*
- Tuy nhiên, điểm quan trọng nhất trong các bài toán trên là một lựa chọn sẽ ảnh hưởng tới toàn bộ những lựa chọn có thể có trong tương lai. Chọn cách nào thì bị giới hạn trong những khả năng mở ra được từ cách đó.
- Ví dụ: [chèn sau]

Nói chung, trong một bài toán tham lam, ta sẽ giải quyết vấn đề bằng cách chọn ra lựa chọn *tốt nhất* **ngay trước mắt**, tức không cần quan tâm lựa chọn này sẽ tác động như thế nào trong tương lai?

Đánh giá tốt/ xấu như thế nào? Định nghĩa một cách toán hơn? ... (bổ sung sau)

## Gàu nước
Đem gàu đựng dư cũng được, chỉ cần chứa được nước thôi mà?
Chỉ dùng gàu $5$. Số gàu cần dùng: $\lceil \frac{L}{5} \rceil$ (chia $5$ làm tròn lên)

## Mua xăng
Tính theo đơn giá:
- Loại $I$ dùng $a$ đồng mua được $1l$
- Loại $II$ dùng $b/2$ đồng mua được $1l$ (suy ra từ đề)

So sánh $a$ và $b/2$, loại nào rẻ hơn thì mua.
**Lưu ý:** Chỉ trong bài này mới đúng được vì hai loại lần lượt là $1l$ và $2l$. Nếu là $3l$ và $5l$, $5l$ và $11l$ thì câu chuyện sẽ khác ...

**Lưu ý 2:** Dù bảo là tính theo đơn giá rồi mua loại rẻ hơn, trong thực tế nếu mua loại II thì phải mua $2l$, chứ không có kiểu: "Tôi đưa nửa tiền, tôi lấy $1l$ thôi được không?"

Nên để thuận tiện, ta coi như đơn vị bằng $2l$ luôn:
- Loại $I$ dùng $2a$ đồng mua được $2l$
- Loại $II$ dùng $b$ đồng mua được $2l$

Nếu $n$ lẻ, ta mới cộng thêm $a$ sau.

## Câu hỏi số 99
Chọn toàn $9$. Dư ra bao nhiêu thì chọn thêm một chữ số nữa. Ví dụ:
- $n = 27 \rightarrow 3$ số $9$
- $n = 12 \rightarrow 1$ số $9$ và một số $3$
- $n = 7 \rightarrow 1$ số $7$ thôi

### Vì sao đúng?
- Số tạo được có số lượng chữ số nhỏ nhất
- Trong những số có cùng số lượng chữ số nhỏ nhất, số này có chữ số đầu bé hơn hẳn.

**Ví dụ:**
$n = 12$, tối ưu nhất là hai chữ số. Có các số:
$66, 75, 57, 48, 84, 39, 93$
Chọn $39$ là tốt nhất.

## Sửa điểm?
Chọn môn điểm thấp nhất, sửa thành $10$

## Mua sách
**Ý tưởng:** Cứ chọn ba quyển đắt nhất chưa mua, mua chúng, thì tiền miễn phí cũng cao nhất có thể (quyển đắt thứ ba còn lại).

**Triển khai:**
Sắp xếp giảm dần. Sau đó lấy tổng $a_3, a_6, a_9, \dots$

Các bài còn lại liên quan tới sort: [Training VKU](https://docs.google.com/document/d/1peW0BLbRYt9ZREec3wWb2qqFsAJjayrBn3BGca1X22M/edit?usp=sharing)