h309. 零钱最少枚数

题目描述

给定 $n$ 种硬币面额和目标金额 $T$。每种硬币可以使用任意多枚，求恰好凑出 $T$ 所需的最少硬币数。

如果无法恰好凑出，输出 $-1$。

输入格式

第一行输入两个整数 $n,T$。

第二行输入 $n$ 个正整数，表示硬币面额。

输出格式

输出最少硬币数，或输出 $-1$。

数据范围

• $1\le n\le 20$
• $1\le T\le 100000$
• $1\le c_i\le 10000$

样例

3 15
1 5 12

3

标签：动态规划、完全背包