🎯 Thuật toán tham lam

Giả sử bạn cần trả lại 41 nghìn tiền thối, với các mệnh giá 1, 5, 10, 20, 50 (nghìn). Cách tự nhiên nhất: lấy tờ lớn nhất còn nhỏ hơn hoặc bằng số tiền còn lại, lặp lại đến khi hết - 20 + 20 + 1 = 41, đúng 3 tờ. Đó chính là thuật toán tham lam (greedy): ở mỗi bước, chọn lựa chọn tốt nhất ngay trước mắt, không suy tính hay quay lại xem xét các lựa chọn khác.

def coin_change_greedy(coins, amount):
    coins = sorted(coins, reverse=True)
    count = 0
    for coin in coins:
        count += amount // coin      # lấy tối đa số tờ mệnh giá này
        amount %= coin
    return count if amount == 0 else -1

So với quy hoạch động (trang trước) - vốn phải xét và lưu lại tất cả các bài toán con trước khi kết luận - tham lam không hề nhìn lại, chỉ đi thẳng một mạch. Đây là lý do tham lam thường đơn giản hơn và chạy nhanh hơn DP rất nhiều.

Cái giá phải trả: đôi khi tham lam sai

Vấn đề là: chọn tốt nhất tại từng bước không phải lúc nào cũng dẫn đến kết quả tốt nhất toàn cục. Vẫn ví dụ đổi tiền, nhưng đổi mệnh giá thành [1, 20, 50] và cần đổi 60: tham lam chọn 50 + 1×10 = 11 tờ, trong khi đáp án tối ưu chỉ cần 20 + 20 + 20 = 3 tờ. Thuật toán tham lam “mù quáng” chọn tờ 50 lớn nhất ngay từ đầu, và không có cách nào “hối hận” quay lại sửa - đây chính là hạn chế cố hữu của greedy: không xét lại quyết định đã đưa ra.

Vậy khi nào tin tưởng được tham lam? Cần chứng minh được tính chất lựa chọn tham lam (greedy-choice property): lựa chọn tốt nhất tại một bước luôn có thể mở rộng thành nghiệm tối ưu toàn cục - tức là không có tình huống nào việc “nhường” lựa chọn tốt nhất lúc này lại giúp về sau tốt hơn. Chứng minh tính chất này thường không dễ (hay dùng kỹ thuật phản chứng hoặc quy nạp), nhưng có một cách thực dụng hơn: nếu chưa chắc, hãy thử tìm phản ví dụ (như ví dụ mệnh giá [1, 20, 50] ở trên) - tìm được một phản ví dụ là đủ để biết tham lam không dùng được, còn phải giải bằng DP.

Fractional Knapsack - cái túi cho phép lấy một phần

Giống 0-1 Knapsack, nhưng lần này được phép lấy một phần của một món đồ (giá trị tính theo tỷ lệ trọng lượng lấy). Trực giác: nếu được lấy một phần, không có lý do gì để bỏ qua phần có “giá trị trên mỗi đơn vị trọng lượng” cao nhất trước - luôn ưu tiên nhét đầy túi bằng những phần “đắt giá nhất” trước.

def fractional_knapsack(weights, values, capacity):
    # Sắp theo giá trị/trọng lượng giảm dần - "đắt" nhất lấy trước
    items = sorted(zip(weights, values), key=lambda x: x[1] / x[0], reverse=True)
    total = 0.0
    for w, v in items:
        if w <= capacity:
            total += v                      # lấy trọn món này
            capacity -= w
        else:
            total += v * (capacity / w)     # hết chỗ -> lấy một phần vừa đủ
            break
    return total

Vì sao chắc chắn đúng ở đây? Vì không giống bản 0-1 (phải lấy nguyên món hoặc không lấy gì), phiên bản cho phép lấy một phần loại bỏ hoàn toàn rủi ro “lỡ mất cơ hội vì hết chỗ” - luôn có thể lấy đúng phần còn thiếu của món đang xét mà không ảnh hưởng đến các món khác đã chọn.

Max Capacity - container chứa được nhiều nước nhất

Cho một dãy cột có chiều cao khác nhau, chọn 2 cột để tạo thành một “bể chứa nước” có diện tích lớn nhất (diện tích = khoảng cách giữa 2 cột × chiều cao cột thấp hơn).

Cách brute-force xét mọi cặp cột tốn O(n²). Cách tham lam dùng hai con trỏ bắt đầu từ hai đầu, thu hẹp dần: luôn di chuyển con trỏ đang trỏ vào cột thấp hơn - vì giữ nguyên cột thấp và di chuyển cột cao chỉ có thể làm diện tích nhỏ đi hoặc bằng (khoảng cách giảm, chiều cao giới hạn vẫn là cột thấp), nên không bao giờ đáng thử.

def max_capacity(heights):
    left, right = 0, len(heights) - 1
    best = 0
    while left < right:
        h = min(heights[left], heights[right])
        best = max(best, h * (right - left))
        if heights[left] < heights[right]:   # cột trái thấp hơn -> di chuyển nó
            left += 1
        else:
            right -= 1
    return best  # O(n), so với O(n²) brute-force

Max Product Cutting - cắt chuỗi để tích lớn nhất

Cho một số nguyên dương n, cắt thành ít nhất 2 phần nguyên dương sao cho tích các phần lớn nhất. Ý tưởng tham lam đến từ quan sát toán học: cắt càng nhiều số 3 càng tốt (vì 3 cho tỷ lệ tích/tổng cao nhất trong các số nguyên >= 2), phần dư ra xử lý riêng (dư 1 thì gộp với một số 3 thành 2+2 để tránh nhân với 1 vô ích; dư 2 thì giữ nguyên một phần bằng 2).

def max_product_cutting(n):
    if n <= 3:
        return n - 1          # base case nhỏ
    product = 1
    while n > 4:
        product *= 3
        n -= 3
    return product * n        # phần còn lại (2, 3, hoặc 4) nhân nốt

Tóm tắt

Tham lam chọn phương án tốt nhất tại từng bước và không bao giờ xét lại - đơn giản, nhanh, nhưng chỉ đúng khi bài toán có tính chất lựa chọn tham lam.
Khi tham lam đúng, nó thường nhanh hơn hẳn DP (không cần bảng, không cần nhớ lại); khi sai, nó cho một đáp án “trông hợp lý” nhưng không tối ưu - nguy hiểm hơn cả một thuật toán chạy chậm, vì lỗi khó nhận ra bằng mắt thường.
Cách thực dụng để kiểm tra: thử tìm phản ví dụ. Không tìm được không có nghĩa là đúng, nhưng tìm được một phản ví dụ là đủ để loại bỏ hướng tham lam.