Thuật toán tham lam (greedy algorithm) thường được sử dụng để giải quyết các bài toán tối ưu hóa (optimization problem). Nguyên lý của nó là đưa ra các quyết định tối ưu cục bộ (locally optimal decision) ở mỗi giai đoạn đưa ra quyết định với hy vọng đạt được lời giải tối ưu toàn cục (globally optimal solution).
Thuật toán tham lam liên tục đưa ra hết lựa chọn tham lam này đến lựa chọn tham lam khác, chuyển đổi bài toán thành một bài toán con nhỏ hơn trong mỗi lượt cho đến khi bài toán được giải quyết.
Thuật toán tham lam không chỉ đơn giản để triển khai mà còn có hiệu quả giải quyết bài toán cao. So với quy hoạch động (dynamic programming), thuật toán tham lam thường có độ phức tạp thời gian thấp hơn.
Trong bài toán đổi tiền xu, đối với một số tổ hợp tiền xu nhất định, thuật toán tham lam có thể đảm bảo tìm được lời giải tối ưu; tuy nhiên, đối với các tổ hợp tiền xu khác, thuật toán tham lam có thể tìm ra những lời giải rất tệ.
Các bài toán phù hợp để giải quyết bằng thuật toán tham lam có hai tính chất lớn: tính chất lựa chọn tham lam (greedy choice property) và cấu trúc con tối ưu (optimal substructure). Tính chất lựa chọn tham lam thể hiện tính hiệu quả của chiến lược tham lam.
Đối với một số bài toán phức tạp, việc chứng minh tính chất lựa chọn tham lam không hề đơn giản. Một cách tương đối, việc bác bỏ nó dễ dàng hơn, ví dụ như trong bài toán đổi tiền xu.
Giải quyết các bài toán tham lam chủ yếu gồm ba bước: phân tích bài toán, xác định chiến lược tham lam và chứng minh tính đúng đắn. Trong số đó, việc xác định chiến lược tham lam là bước cốt lõi, còn chứng minh tính đúng đắn thường là khó khăn chính.
Bài toán cái túi phân số (fractional knapsack problem), dựa trên bài toán cái túi 0-1 (0-1 knapsack problem), cho phép lựa chọn các phần của vật phẩm, và do đó có thể được giải quyết bằng thuật toán tham lam. Tính đúng đắn của chiến lược tham lam có thể được chứng minh bằng chứng minh phản chứng (proof by contradiction).
Bài toán dung tích lớn nhất (max capacity problem) có thể được giải quyết bằng phương pháp duyệt vét cạn với độ phức tạp thời gian \(O(n^2)\). Bằng cách thiết kế một chiến lược tham lam để dịch chuyển cạnh ngắn hơn vào trong ở mỗi lượt, độ phức tạp thời gian có thể được tối ưu hóa thành \(O(n)\).
Trong bài toán phân chia đạt tích lớn nhất (maximum product cutting problem), chúng ta lần lượt rút ra hai chiến lược tham lam: tất cả các số nguyên \(\geq 4\) đều nên tiếp tục được phân chia, và thừa số phân chia tối ưu là \(3\). Mã nguồn bao gồm các phép toán lũy thừa, và độ phức tạp thời gian phụ thuộc vào phương pháp triển khai phép lũy thừa, thường là \(O(1)\) hoặc \(O(\log n)\).