Lý thuyết

• Bài toán tối ưu: Cho các lựa chọn, hành động khác nhau. Mỗi lựa chọn có nhiều yếu tố: lợi ích đem lại, khả năng thực hiện nó, tác động tới lựa chọn khác trong tương lai, ... Thực hiện chiến thuật nào để kết quả đạt lớn nhất hoặc nhỏ nhất?
• Giải thuật Tham lam (greedy): Chỉ nhìn một bước, tìm cái tốt nhất ngay trước mắt, 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. Ví dụ:
  • Bài "Xóa chữ số": cứ xóa chữ số lớn nhất
  • Bài "Câu hỏi số 99": chọn nhiều chữ số \(9\) nhất có thể
  • ...
• Tham lam là hướng tiếp cận đơn giản, dễ nghĩ ra nhất cho "Bài toán tối ưu" nêu ở trên. Chỉ đúng được một số bài đặc biệt. Để biết có đúng hay không, ta cứ thử code và nộp lên xem kết quả chấm, "hi vọng là nó đúng". Cách khác chắn chắn hơn (nhưng rất khó) là chứng minh toán học.
• Một số bài ở đây cần kiến thức toán.