TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1065
  • 题目
  • P1065硬币找零
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

    在现实生活中,我们经常遇到硬币找零的问题,例如,在发工资时,财务人员就需要计算最少的找零硬币数,以便他们能从银行拿回最少的硬币数,并保证能用这些硬币发工资。
    我们应该注意到,人民币的硬币系统是100,50,20,10,5,2,1,0.5,0.2,0.1,0.05,0.02,0.01元,采用这些硬币我们可以对任何一个工资数用贪心算法求出其最少硬币数。
    但不幸的是:我们可能没有这样一种好的硬币系统,因此用贪心算法不能求出最少的硬币数,甚至有些金钱总数还不能用这些硬币找零。例如,如果硬币系统是40,30,25元,那么37元就不能用这些硬币找零;95元的最少找零硬币数是3。又如,硬币系统是10,7,5,1元,那么12元用贪心法得到的硬币数为3,而最少硬币数是2。
    你的任务就是:对于任意的硬币系统和一个金钱数,请你编程求出最少的找零硬币数;如果不能用这些硬币找零,请给出一种找零方法,使剩下的钱最少。

    输入格式

    第1行,为N和T,其中1≤N≤50为硬币系统中不同硬币数;1≤T≤100000为需要用硬币找零的总数。
    第2行为N个数值不大于65535的正整数,它们是硬币系统中各硬币的面值。

    输出格式

    请输出最少的找零硬币数。

    样例输入

    4 12 
    10 7 5 1 

    样例输出

    2