#P1658. 购物
购物
题目描述
你就要去购物了,现在你手上有 种不同面值的硬币,每种硬币有无限多个。为了方便购物,你希望带尽量少的硬币,但要能组合出 到 之间的任意值。
输入格式
第一行两个数 ,以下 个数,表示每种硬币的面值。
输出格式
最少需要携带的硬币个数,如果无解输出 -1
。
20 4
1 2 5 10
5
提示
对于 的数据,满足 ,;
对于 的数据,满足 ,。
你就要去购物了,现在你手上有 N 种不同面值的硬币,每种硬币有无限多个。为了方便购物,你希望带尽量少的硬币,但要能组合出 1 到 X 之间的任意值。
第一行两个数 X,N,以下 N 个数,表示每种硬币的面值。
最少需要携带的硬币个数,如果无解输出 -1
。
20 4
1 2 5 10
5
对于 30% 的数据,满足 N≤3,X≤20;
对于 100% 的数据,满足 N≤10,X≤103。