DP-Bài toán chiếc balo

ĐỀ BÀI: DP - BÀI TOÁN CHIẾC BALO 5 (UNBOUNDED KNAPSACK / COIN CHANGE)

Trong siêu thị có \(n\) loại đồ vật, mỗi loại có số lượng vô hạn và đồ vật thứ \(i\) có trọng lượng là \(w[i]\).

Tên trộm mang theo một chiếc túi có sức chứa tối đa là \(M\). Tên trộm muốn lấy đủ tổng trọng lượng đúng bằng \(M\) sao cho tổng số lượng đồ vật lấy ra là ít nhất.

Yêu cầu: Tìm số lượng đồ vật ít nhất để đạt được tổng trọng lượng đúng bằng \(M\). Nếu không có cách nào tạo thành tổng \(M\), in ra -1.

Dữ liệu vào:

• Dòng 1: Chứa hai số nguyên dương \(n\) và \(M\) (\(1 \le n \le 100\), \(1 \le M \le 10^6\)).
• Dòng 2: Chứa \(n\) số nguyên dương \(w[1], w[2], \dots, w[n]\) (\(1 \le w[i] \le 10^6\)).

Dữ liệu ra:

• In ra một số nguyên duy nhất là số đồ vật ít nhất cần lấy, hoặc -1 nếu không có cách nào.

Ví dụ:

Input

3 11
1 5 7

Output

3

Giải thích: \(11 = 5 + 5 + 1\) (sử dụng 3 đồ vật).