有6种面值的货币，最小的是1，求出用最少的货币数凑成1..100的最少货币数，输出其中的最大值和他们的平均值。而可以用减法。
例如：6=1+2+3,6=7-1，那么凑成6的最小货币数为2.
是一个没有下限的背包问题，体积数组开到3000+就可以了（经过试验了）。
View Code
1 program pku1252(input,output);
2 var
3 f : array[-3000..3000] of longint;
4 v : array[1..6] of longint;
5 cases,e : longint;
6 procedure init;
7 var
8 i : longint;
9 begin
10 for i:=1 to 6 do
11 read(v[i]);
12 readln;
13 fillchar(f,sizeof(f),63);
14 f[0]:=0;
15 end; { init }
16 function min(aa,bb : longint ):longint;
17 begin
18 if aa>bb then
19 exit(bb);
20 exit(aa);
21 end; { min }
22 procedure main;
23 var
24 i,j : longint;
25 begin
26 for i:=1 to 6 do
27 begin
28 for j:=v[i]-3000 to 3000 do
29 f[j]:=min(f[j],f[j-v[i]]+1);
30 for j:=3000-v[i] downto -3000 do
31 f[j]:=min(f[j],f[j+v[i]]+1);
32 end;
33 end; { main }
34 procedure print;
35 var
36 i,max,sum : longint;
37 begin
38 sum:=0;
39 max:=0;
40 for i:=1 to 100 do
41 begin
42 inc(sum,f[i]);
43 if f[i]>max then
44 max:=f[i];
45 end;
46 writeln((sum/100):0:2,' ',max);
47 end; { print }
48 begin
49 readln(cases);
50 for e:=1 to cases do
51 begin
52 init;
53 main;
54 print;
55 end;
56 end.