问题2308--购物

2308: 购物

时间限制: 1 Sec  内存限制: 128 MB
提交: 12  解决: 11
[提交] [状态] [讨论版] [命题人:]

题目描述

你就要去购物了，现在你手上有 N 种不同面值的硬币，每种硬币有无限多个。为了方便购物，你希望带尽量少的硬币，但要能组合出 1 到 X 之间的任意值。

输入

第一行两个数 X，N，以下 N 个数，表示每种硬币的面值。

输出

最少需要携带的硬币个数，如果无解输出 -1。

样例输入 Copy 

20 4
1 2 5 10

样例输出 Copy 

5

提示

说明/提示
对于 30% 的数据，满足 N ≤3，X ≤ 20；
对于 100% 的数据，满足 N ≤ 10，X ≤ 103。
题目来自洛谷P1658

来源/分类

贪心算法 
[提交] [状态]