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的正整数,它们是硬币系统中各硬币的面值。

    输出格式

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

    样例输入 1

    4 12 
    10 7 5 1 

    样例输出 1

    2

    样例输入 2

    50 100000
    1843 306 257 212 159 150 144 122 116 107 96 78 74 72 70 66 55 50 49 47 46 45 44 43 42 40 39 37 36 34 33 29 28 27 26 25 24 23 20 18 16 15 11 10 9 8 7 6 5 4 

    样例输出 2

    57

    样例输入 3

    10 137
    52 49 40 31 19 17 14 8 7 1 

    样例输出 3

    4