P15028

凑硬币

难度 5 级小学动态规划入门背包DP 完全背包

讨论统计 27通过 58提交 46.6%通过率旧版界面

时间限制 1 秒 内存限制 128 MB

题目描述

小明在超市兼职收银员，现有 $n$ 种硬币，第 $i$ 种硬币的面值为 $a_i$ ，硬币面值之间互质。每种硬币有无穷多个。小明现需要给顾客找回 $s$ （用 $n$ 种硬币组成 $s$ 元），求问最少可以用几枚硬币。

第一行为两个整数 $n$ 和 $s$ 。第二行为 $n$ 个整数 $a_i$ 。

一个整数，表示所需要的最少硬币数量。

样例 1

输入

3 27
2 5 7

输出

对于100%的数据， $n\leq50,s\leq10000$ 。

动规专题

上一题下一题