Đổi tiền ít tờ nhất

Trung bình

quy hoạch động6 test · 3 giây

Có n loại mệnh giá (mỗi loại dùng không giới hạn số tờ). Cần ít nhất bao nhiêu tờ để được đúng X đồng? Nếu không thể, in -1.

Tham lam (luôn lấy tờ lớn nhất) sai với mệnh giá {1, 3, 4} và X = 6. Hãy dùng quy hoạch động: dp[v] = min(dp[v − c] + 1).

Dữ liệu vào

Dòng 1: n X (1 ≤ n ≤ 100, 0 ≤ X ≤ 10⁴).

Dòng 2: n mệnh giá (1 ≤ cᵢ ≤ 10⁴).

Số tờ ít nhất, hoặc -1.

Input

3 6
1 3 4

Output

3 + 3 = 6 (2 tờ). Tham lam 4 + 1 + 1 cần 3 tờ.

Input

1 3
2

Output

-1

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.