BBOI-2第四题《硬币找零》

大榕树 \ 信息学奥赛 \ 网上竞赛

BBOI-2第四题《硬币找零》

原文链接：http://www.mydrs.org/program/list.asp?id=428
第四题硬币找零。 (30分)
在现实生活中，我们经常遇到硬币找零的问题。人民币的硬币系统是100，50，20，10，5，2，1，0.5，0.2，0.1，0.05，0.01元，采用这些硬币我们可以对任何一个款项用贪心算法求出其最少的硬币。
但是不幸的是，我们没有这么好的硬币系统。比如说硬币系统是40，30，25元，那么37元就不能找零；95最少找零数是3。又如，硬币系统是10，7，5，1元，那么12元用贪心算法找得的硬币数是3，而最少硬币数是2。
你的任务是，对于给定的硬币系统(共n中硬币,1<=n<=5000)和一个金钱数 t (1<=t<=30000，找出最少的找零硬币数；如果不能用这些硬币找零，则给出一种找零方法，使剩下的钱最少。
输入：n t (input4.txt)
硬币系统里的n种硬币的面值
输出：如果 t 能被硬币系统中的硬币找零，请输出最少的找零硬币数。
如果 t 不能被找零，请输出剩下的钱最少的找零方案中的最少硬币数。
例如：输入 4 12
10 7 5 1
输出 2
输入 3 39
30 20 10
输出 1
输入 3 80
300 200 100
输出 0

作者：
来源：
时间：2002-10-02

上一篇：BBOI-2第三题《最长的子串》
下一篇：