邮票问题pascal

Description

设有已知面额的邮票m种，每种有n张。用总数不超过n张的邮票进行组合，能组合的邮票面额中可以连续出现面额最多有多少？

Input

第一行：n和m的值，中间用一个空格隔开
第二行：有m种邮票的面额（1<=邮票面额<=255），数与数之间用一个空格隔开
( 1 < n <= 20 ，1 < m <= 20 )

Output

只有一行且只有一个正整数：连续面额数的最大值

Sample Input

4 3 1 2 4

Sample Output

14

Source

基础

请高手赐教

不简单啊

一看到这个题目,给人的第一感觉是用回溯算法,从面额1开始,每种面额都用回溯进行判断,算法复杂度并不高,但是当m,n取到极限值100时,程序明显超时,因此,回溯算法在这里并不可取. 能否用递推完成呢?我们有一个思路:从面额1开始,建立递推关系方程,就用范例来说吧,面额1,2,4只用1张邮票行了,面额3可以表示为面额1,2的邮票和1+1=2,面额5有两种表示方式MIN(面额1+面额4,面额2+面额3),照此类推,递推关系方程不难建立,由于1<=邮票面额<=255,1<=n<=100,因此MAX值最多可达到25500,25500次循环里必定还有嵌套循环,因此算法不加优化,很难在规定时间内得出最优值.这就需要递推的算法优化. 一味递推不寻求算法优化,速度较之搜索提高不少,但一旦数据规模过大,很难在规定时间内得出最优值.就拿邮票问题来说,以下是递推的一种方法:  {$A+,B-,D-,E+,F-,G-,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V-,X+,Y-} {$M 16384,0,655360}  program stamps; var f,fout:text; n,m,i,j,k:integer;  c:array [1..255] of integer; {面额}  a:array [1..31000] of integer; {递推数组}  bl:boolean;  procedure readfile; {读文件}  begin assign(f,'STAMP.DAT');  reset(f); assign(fout,'STAMP.OUT'); rewrite(fout); readln(f,n);  readln(f,m); bl:=true; for i:=1 to m do  begin readln(f,c[i]); if c[i]=1 then bl:=false; end; close(f); end;  procedure work; begin if bl=true then write(fout,'MAX=0') {不存在面额1时输出无解}  else begin i:=1; a[i]:=1;  repeat  i:=i+1;  for j:=1 to m do  if ((i mod c[j]=0) and ((i div c[j])<a[i]))  or (a[i]=0) {判断它能否被题目给定面额整除} then  a[i]:=i div c[j]; for j:=1 to trunc(i/2) do if (a[j]+a[i-j]<a[i]) then a[i]:=a[j]+a[i-j]; {寻找(1<=j<=i),使A[j]+A[i-j]值最小} until (a[i]>n) or (a[i]=0); write(fout,'MAX=',i-1); {输出} end; close(fout); end; begin readfile; work; end. 这种递推方法原理是:对于某种要求得到的面额,判断它能否被题目给定面额整除，再寻找(1<=j<=i),使A[j]+A[i-j]值最小,求出凑成某种面额最少邮票数,算法虽然简单,但还可以进一步优化.何不将用m种面额邮票作循环,建立递推关系式:A[i]=MAX(A[I-C[j]]+1),于是当取到极限值时,程序循环减少了约1.6*10^8次循环,递推优化作用不言而喻,下面是改进后的程序:  {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V-,X+} {$M 16384,0,655360} program stamps_pro; uses crt; var x:array [1..255] of byte; pieces:array [0..30000] of byte; max,m,n,i,j:integer; filename:string; f:text; begin {读文件} assign(f,'STAMP.DAT'); reset(f); readln(f,n); readln(f,m); for i:=1 to m do readln(f,x[i]); close(f); fillchar(pieces,sizeof(pieces),0); max:=0; {递推循环}  repeat max:=max+1; {循环,建立递推关系式PIECES[i]=MAX(PIECES[I-X[j]]+1)} for i:=1 to m do if max-x[i]>=0 then begin if pieces[max]=0 then pieces[max]:=pieces[max-x[i]]+1; if pieces[max]>pieces[max-x[i]]+1  then pieces[max]:=pieces[max-x[i]]+1; end; {输出无解} if (pieces[max]=0) or (pieces[max]>n) then begin writeln('MAX=',max-1); exit; end; until false; end. 程序优化后,运行四组测试数据时间如下: (测试机型:Pentium MMX 233)  测试数据 m N 未优化程序运行时间(秒) 优化程序运行时间(秒)  1 5 10 0.05 0.11  2 3 5 0.06 0.11  3 10 20 0.61 0.17  4 70 65 6.75 0.33  5 100 100 20.20 1.20