Video
Bài toán đổi tiền: tham lam hay quy hoạch động?
Đổi tiền: lấy tờ lớn nhất trước có luôn ra ít tờ nhất không?
Hoạt động
Sinh viên tìm được phản ví dụ cho cách đổi tiền tham lam, và nói được khi nào tham lam an toàn.
Mỗi nhóm nộp một hệ mệnh giá và một số tiền làm tham lam sai, kèm hai cách đổi để so sánh. Nhóm phải tự tính, không chép từ AI.
Hãy bênh vực cách đổi tiền tham lam: luôn lấy mệnh giá lớn nhất còn được. Tôi sẽ thử thách bạn bằng các hệ mệnh giá. Chỉ nhận sai khi tôi đưa ra một số tiền cụ thể mà tham lam cho kết quả nhiều đồng hơn cách tối ưu, và tự tính lại để kiểm tra.
Hệ 1, 5, 10, 25 là ví dụ quen thuộc mà tham lam vẫn đúng. Có thể dùng để các nhóm đối chiếu ở bước 4.