Question

pascal找零问题！急急急！！！！！！！

Description
乔治是商店的店主，他一共有四种硬币：25美分，10美分，5美分，1美分。已知四种硬币的个数。乔治现在需要找给某个顾客C美分零钱，请问用这些硬币组合，能否得到 C，如果能，使用硬币最少的情况下，怎么组合？
Input
输入包括多行，每行都按如下格式：
Q D N P C
Q 是25美分的硬币个数，D是10美分的硬币个数，N是5美分的硬币个数，P是1美分的硬币个数，C是要找给顾客的零钱（0到99之间）。当输入的一行包括5个0时结束程序。
Output
对于每组数据，如果能够刚好凑足零钱找给顾客，你必须输出：
Dispense # quarters, # dimes, # nickels, and # pennies.
否则输出：
Cannot dispense the desired amount.
Sample Input
5 9 9 9 37
0 9 9 9 37
10 10 10 0 37
1 3 0 10 30
1 3 6 10 30
0 0 0 0 0
Sample Output
Dispense 1 quarters, 1 dimes, 0 nickels, and 2 pennies.
Dispense 0 quarters, 3 dimes, 1 nickels, and 2 pennies.
Cannot dispense the desired amount.
Dispense 0 quarters, 3 dimes, 0 nickels, and 0 pennies.
Dispense 1 quarters, 0 dimes, 1 nickels, and 0 pennies.
Source

Answer 1

就是个普通的深搜，不习惯C语言的数组，下面的程序按照我个人习惯编写的，测试无误。另外我问下这个题是哪里的？ program change;
var
tot,sum,k:integer;
num,tmp,result:array[1..5]of integer;
success:boolean;function can:boolean;
begin
for k:=1 to 5 do if num[k]<>0 then exit(true);
exit(false);
end;procedure dfs(dep,remained:integer);
var
i,j:integer;
begin
if dep=5 then
begin
if remained=0 then
begin
sum:=tmp[1]+tmp[2]+tmp[3]+tmp[4];
if sum<tot then
begin
for i:=1 to 4 do result[i]:=tmp[i];
tot:=sum;
end;
success:=true;
end;
exit;
end;

for j:=0 to num[dep] do
begin
tmp[dep]:=j;
if dep=1 then dfs(dep+1,remained-25*j)
else if dep=2 then dfs(dep+1,remained-10*j)
else if dep=3 then dfs(dep+1,remained-5*j)
else if dep=4 then dfs(dep+1,remained-j);
end;

end;begin
for k:=1 to 5 do read(num[k]);
readln;
while can do
begin
tot:=100000;
success:=false;
dfs(1,num[5]);
if success then writeln('Dispense ',result[1],' quarters, ',result[2],' dimes, ',result[3],' nickels, and ',result[4],' pennies.')
else writeln('Cannot dispense the desired amount.');
for k:=1 to 5 do read(num[k]);
readln;
end;
end.