问题 4207 --最少硬币组成

4207: 最少硬币组成

题目描述

  从n种币值为a[1..n]的硬币中,任选几个硬币组成价值为V的一堆货币,问最少需要几个硬币?其中每种硬币的数量没有限制。1<=n<=100,1<=v<=100000,1<=a[i]<=100000

输入

输入文件中有两行:第一行有两个数v和n;第二行有n个以空格分隔的数,表示n个币值.

输出

输出文件中只有一行,该行只有一个数,表示所需的最少硬币数, 如果无论如何选取硬币,均不能得到币值v,则输出0.

样例输入输出

输入#1 复制 
20 4
8 9 3 1
输出#1 复制 
3

提示

发表题解
序号 标题 作者 发表时间 费用 订购数 操作

题目信息

提交
难度
普及/提高-
标签
点击显示
递交数
14
已通过
4
通过率
29%
时间限制
1 秒
内存限制
128 MB
来源
收藏