硬币找零

<div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> 在现实生活中，我们经常遇到硬币找零的问题，例如，在发工资时，财务人员就需要计<span style="line-height:1.5;">算最少的找零硬币数，以便他们能从银行拿回最少的硬币数，并保证能用这些硬币发工资。</span> </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> 我们应该注意到，人民币的硬币系统是 100，50，20，10，5，2，1，0.5，0.2，0.1，0.05， </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> 0.02，0.01 元，采用这些硬币我们可以对任何一items工资数用贪心算法求出其最少硬币数。&nbsp; </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> 但不幸的是： 我们可能没有这样一种好的硬币系统， 因此用贪心算法不能求出最少的硬币数，<span style="line-height:1.5;">甚至有些金钱总数还不能用这些硬币找零。例如，如果硬币系统是 40，30，25 元，那么 37</span><span style="line-height:1.5;">元就不能用这些硬币找零；95 元的最少找零硬币数是 3。又如，硬币系统是 10，7，5，1</span><span style="line-height:1.5;">元，那么 12 元用贪心法得到的硬币数为 3，而最少硬币数是 2。&nbsp;</span> </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> 你的任务就是：对于任意的硬币系统和一items金钱数，请你编程求出最少的找零硬币数； </div> <div style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;background-color:#FFFFFF;"> 如果不能用这些硬币找零，请给出一种找零方法，使剩下的钱最少。&nbsp; </div>

<span style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;line-height:21px;background-color:#FFFFFF;">输入数据：&nbsp;</span><br /> <span style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;line-height:21px;background-color:#FFFFFF;">Page 1 行，为 N 和 T，其中 1≤N≤50 为硬币系统中不同硬币数；1≤T≤100000 为需要用硬币找零的总数。&nbsp;</span><br /> <span style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;line-height:21px;background-color:#FFFFFF;">Page 2 行为 N items数值不大于 65535 的正整数，它们是硬币系统中各硬币的面值。</span><br /> <span style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;line-height:21px;background-color:#FFFFFF;">当n，t同时为0时结束。</span>

<span style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;line-height:21px;background-color:#FFFFFF;">输出数据：&nbsp;</span><br /> <span style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;line-height:21px;background-color:#FFFFFF;">如 T 能被硬币系统中的硬币找零，请输出最少的找零硬币数。&nbsp;</span><br /> <span style="color:#464646;font-family:Tahoma, Arial, sans-serif, simsun;font-size:14px;line-height:21px;background-color:#FFFFFF;">如 T 不能被硬币系统中的硬币找零，请输出剩下钱数最少的找零方案中的最少硬币数。</span>