《硬币找零》参考程序

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

《硬币找零》参考程序

原文链接：http://www.mydrs.org/program/list.asp?id=433

第四题硬币找零。 (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.

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

上一篇：FOI&BBOI-2结果公布
下一篇：《神奇国度》参考程序