Thuật toán tham lam là thuật toán mà ở mỗi bước chọn biến thể tối ưu (trong bước hiện tại) với kỳ vọng rằng giải pháp cuối cùng sẽ tối ưu theo nghĩa toàn cục.
Ví dụ nhỏ:
Giả sử chúng ta có vô số đồng xu có mệnh giá khác nhau và chúng ta cần thu thập số tiền S. Hãy xem xét hai trường hợp cụ thể, mỗi trường hợp chúng ta sẽ cố gắng giải quyết bằng thuật toán tham lam.
Cụ thể, chúng tôi sẽ hành động như sau: ở mỗi bước, chúng tôi sẽ lấy một đồng xu có mệnh giá cao nhất (tùy chọn tốt nhất trong bước), không vượt quá số tiền còn lại.
a) Gọi các mệnh giá đồng xu là 1, 5 và 10 và S = 27.
1) Lấy 10, S: 27 -> 17
2) Lấy 10, S: 17 -> 7
3) Lấy 5, S: 7 -> 2
4) Lấy 1, S: 2 -> 1
5) Lấy 1, S: 1 -> 0
Kết quả là họ đã ghi được số tiền là năm xu. Bạn có thể độc lập (ví dụ: bạo lực) đảm bảo rằng với 4 đồng xu trở xuống, bạn sẽ không thể đạt điểm 27.
b) Gọi mệnh giá của các đồng xu là 1, 5 và 7 và S = 24.
1) Lấy 7, S: 24 -> 17
2) Lấy 7, S: 17 -> 10
3) Lấy 7, S: 10 -> 3
4) Lấy 1, S: 3 -> 2
5) Lấy 1, S: 2 -> 1
6) Lấy 1, S: 1 -> 0.
Chúng tôi ghi điểm với sáu đồng xu, nhưng có thể ghi điểm S với bốn đồng xu - hai đồng xu có mệnh giá 7 và hai đồng xu có mệnh giá 5.
Như có thể thấy từ ví dụ, không phải lúc nào cũng có thể giải các bài toán bằng thuật toán tham lam. Nhưng nếu nó dẫn đến một câu trả lời tối ưu tổng thể, thì nó thường sẽ dễ dàng hơn so với việc sử dụng quy hoạch động hoặc các phương pháp khác.