Hướng dẫn thuật toán

Link bài tập

1. Phân tích đề bài

• Mục tiêu: Tìm số lượng xu ít nhất để tổng bằng .
• Đặc điểm: Một mệnh giá có thể dùng nhiều lần (bài toán Knapsack dạng không giới hạn số lượng).
• Ràng buộc: lên đến , lên đến . Thuật toán cần có độ phức tạp khoảng để chạy kịp thời gian.

2. Ý tưởng thuật toán

Chúng ta sẽ dùng một mảng để lưu trữ kết quả tối ưu của các bài toán con từ đến .

• Gọi dp[i] là số lượng xu tối thiểu để tạo ra tổng bằng i.
• Mục tiêu cuối cùng là tìm giá trị của dp[x].

3. Các bước thực hiện

1. Khởi tạo:

   • Tạo mảng dp có kích thước .
   • Đặt dp[0] = 0 (để có tổng bằng 0 thì cần 0 đồng xu).
   • Tất cả các vị trí khác dp[1...x] khởi tạo bằng một giá trị vô cực (một số lớn hơn , ví dụ: ) để đánh dấu là chưa thể đạt tới.

2. Trạng thái chuyển đổi (Công thức quy hoạch động):

   • Duyệt qua từng giá trị mục tiêu từ đến .
   • Với mỗi giá trị , thử dùng lần lượt từng loại mệnh giá trong danh sách:
     • Nếu và có thể tạo được tổng (tức là khác vô cực):
     • Cập nhật: dp[i] = min(dp[i], dp[i - c_j] + 1).

3. Kết quả:

   • Sau khi lặp xong, kiểm tra giá trị tại dp[x].
   • Nếu dp[x] vẫn là vô cực, in ra -1.
   • Ngược lại, in ra giá trị dp[x].