第四题  硬币找零。 (30分)
    在现实生活中，我们经常遇到硬币找零的问题。人民币的硬币系统是100，60，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

------------------------------------------------------------FOI&BBOI2  2002.10-----

以下是范例程序代码：


program foi_t4;

{
    FOI&BBOI2 Friendship
      OI Test 2002.10

    T4:The Coin Problem
    Write by Fruit Ikari

    E-mail: fruithms@sina.com
    OICQ  : 337972
}


{$S-,Y-,R-,Q-,I-}
{$M 65520,0,655360}
const
   inputfilename='input4.txt';
   outputfilename='output4.txt';
   maxn=5000;
   maxt=30000;
   maxcoin=maxt+1;
var
   coin:array [1..maxn] of word;
   n,t,answer:integer;
   testfile:text;

procedure init;
var
 i:integer;
begin
   assign(testfile,inputfilename); reset(testfile);
   readln(testfile,n,t);
   for i:=1 to n do read(testfile,coin[i]);
   close(testfile);
end;

procedure main;
var
   f:array [0..maxt] of integer;
   temp,i,j,max:integer;
begin
  for i:=1 to t do f[i]:=maxcoin;
  f[0]:=0;
  for i:=1 to t do
  begin
    max:=maxcoin;
    for j:=1 to n do
      if coin[j]<=i then
       begin
         temp:=f[i-coin[j]]+1;
         if temp<max then max:=temp;
       end;
      f[i]:=max;
  end;
 i:=t;
 while f[i]=maxcoin do dec(i);
 answer:=f[i];
end;

procedure show;
begin
  assign(testfile,outputfilename);
  rewrite(testfile);
  writeln(testfile,answer);
  close(testfile);
end;

begin
  init;
  main;
  show;
end.