Phương pháp tham lam (greedy algorithm) là một phương pháp tìm kiếm lời giải bằng cách chọn lựa các bước đi tốt nhất tại mỗi bước mà không cần quan tâm đến các bước tiếp theo. Trong bài toán đổi tiền, phương pháp tham lam sẽ chọn tờ tiền có mệnh giá lớn nhất trước, sau đó tiếp tục với các tờ tiền có mệnh giá nhỏ hơn cho đến khi đạt được tổng số tiền mong muốn.

Để đổi tờ 20k bằng các tờ tiền mệnh giá 1k, 5k, và 8k, ta có thể áp dụng phương pháp tham lam như sau:

1. Chọn tờ tiền có mệnh giá lớn nhất mà không vượt quá số tiền còn lại cần đổi.
2. Trừ số tiền đã đổi từ tổng số tiền cần đổi.
3. Lặp lại bước 1 và 2 cho đến khi tổng số tiền cần đổi bằng 0.

Áp dụng phương pháp này:

1. Bắt đầu với 20k.
2. Chọn tờ 8k (lớn nhất không vượt quá 20k):
- Số tờ 8k: \( \left\lfloor \frac{20}{8} \right\rfloor = 2 \) tờ.
- Số tiền còn lại: \( 20 - 2 \times 8 = 20 - 16 = 4 \)k.
3. Chọn tờ 5k (lớn nhất không vượt quá 4k):
- Số tờ 5k: \( \left\lfloor \frac{4}{5} \right\rfloor = 0 \) tờ.
- Số tiền còn lại: 4k.
4. Chọn tờ 1k (lớn nhất không vượt quá 4k):
- Số tờ 1k: \( \left\lfloor \frac{4}{1} \right\rfloor = 4 \) tờ.
- Số tiền còn lại: \( 4 - 4 \times 1 = 0 \)k.

Vậy, với tờ 20k, áp dụng phương pháp tham lam, ta đổi được:
- 2 tờ 8k
- 0 tờ 5k
- 4 tờ 1k

Tóm lại:
- 2 tờ 8k
- 0 tờ 5k
- 4 tờ 1k