Problem
Cho N
vật phẩm có khối lượng m1, …, mN
. Họ lấp đầy một chiếc ba lô có thể chịu được trọng lượng không quá M
. Làm cách nào để tăng cân đúng M
bằng cách sử dụng càng ít vật phẩm càng tốt?
Đầu vào:
- dòng đầu tiên ghi số tự nhiên N
không quá 100 và số tự nhiên M
không quá 10000;
- dòng thứ hai chứa N
số tự nhiên mi
không vượt quá 100.
Đầu ra: In số lượng vật phẩm nhỏ nhất bạn cần hoặc 0 nếu bạn không đạt được trọng lượng nhất định.
Ví dụ
<đầu>
# |
Đầu vào |
Đầu ra |
điều>
1 |
1 5968
18
|
0 |