Đổi Tiền Ít Xu Nhất
Points
15
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho $N$ loại tiền xu với các mệnh giá $c_1, c_2, \dots, c_N$ (số lượng mỗi loại không giới hạn) và một số tiền mục tiêu $S$. Hãy tìm số lượng đồng xu ít nhất cần dùng để tổng mệnh giá bằng đúng $S$. Nếu không thể đổi được, in ra -1.
Cấu trúc con tối ưu: $dp[x] = \min_{c_i \le x} (dp[x - c_i] + 1)$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N$ và $S$ ($1 \le N \le 100$, $0 \le S \le 10^4$).
- Dòng thứ hai chứa $N$ số nguyên dương $c_1, c_2, \dots, c_N$ ($1 \le c_i \le 10^4$).
Dữ liệu ra
- In ra số xu ít nhất cần dùng, hoặc
-1nếu không thể.
Ví dụ
| Input | Output |
|---|---|
| 3 11\n1 2 5 | 3 |
| 1 3\n2 | -1 |
Giới hạn
- $1 \le N \le 100$
- $0 \le S \le 10^4$
- $1 \le c_i \le 10^4$
Community Discussion