Thuật toán quy hoạch động là gì ???? Trước khi bắt đầu chúng ta sẽ xem một ví dụ thực tế đơn giản để thấy thuật toán "Quy hoạch động" (Dynamic) hoạt động như thế nào và được ứng dụng làm gì!!
1. ĐỀ BÀI
Để tiết kiệm tối đa chi phí vận hành và tăng tốc độ giao dich, các ngân hàng muốn thiết kế một thuật toán cho các cây ATM để cây ATM có thể trả được đúng số tiền dựa trên những loại tiền có trong ATM đó, và số tờ tiền rút ra là nhỏ nhất. Ví dụ : Một cây ATM chỉ còn tiền các mệnh giá 20$, 50$ , một khách hàng muốn rút 110$, thì cây ATM sẽ tính toán và trả 1 tờ 50$ và 3 tờ 20$. Nếu khách hàng muốn rút 60$ thì cây ATM sẽ báo không thực hiện được giao dịch. Hãy viết thuật toán thực hiện yêu cầu trên, đầu ra ghi số lượng tờ tiền rút ra, nếu không thể thực hiện giao dịch, in ra -1.Giới hạn : Số Testcase NT không quá 30, Số loại tiền N không quá 10, Giá trị 1 loại tiền không quá 10000, Số tiền rút ra không quá 1000000.