(连续邮资问题)某国发行了n种不同面值的邮票,并规定每封信上最多允许贴m张邮票。在这些约束下,为了能贴出{1,2,3,…,maxvalue}连续整数集合的所有邮资,并使maxvalue的值最大,应该如何设计各邮票的面值?例如,当n=5和m=4时,面值设计为(1,3,11,15,32),可使maxvalue达到最大值70(或者说,用这些面值的1至4张邮票可以表示不超过70的所有邮资,但无法表示邮资71)。而用其他面值的1至4张邮票如果可以表示不超过k的所有邮资,必有k≤70)
下面是用递归回溯求解连续邮资问题的程序。数组x[1:n]表示n种不同的邮票面值,并约定各元素按下标是严格递增的。数组bestx[1:n]存放使maxvalue达到最大值的邮票面值(最优解),数组y[maxl]用于记录当前已选定的邮票面值x[1:i]能贴出的各种邮资所需的最少邮票张数。请将程序补充完整。
program S502;
const NN=20;
maxint=30000;
maxl=500;
var bestx,x:array [0..NN] of integer;
y:array [0..maxl] of integer;
j,n,m,maxvalue:integer;
procedure result;
var j:integer;
begin
writeln('max=',maxvalue);
for j:=1 to n do write(bestx[j]:4);
writeln;
end;
procedure backtrace(i,r:integer);
var j,k:integer;
z: array[0..maxl] of integer;
begin
for j:=0 to x[i-2]*(m-1) do
if (y[j]<m) then
for k:=1 to m-y[j] do
if (y[j]+k<=y[ j+x[i-1]*k ]) then
y[ j+x[i-1]*k ]:=y[j]+k;
while (y[r]<maxint) do inc(r);
if (i>n) then
begin
if (r-1>maxvalue) then
begin
maxvalue:= r-1 ;
for j:=1 to n do bestx[j]:=x[j];
end;
exit;
end;
for k:=0 to maxl do z[k]:=y[k];
for j:= x[i-1]+1 to r do
begin
x[i]:=j;
backtrace(i+1,r) ;
for k:=0 to maxl do y[k]:=z[k];
end;
end;
begin
maxvalue:=0;
writeln('input n,m:');
readln(n,m);
for j:=1 to maxl do y[j]:=maxint;
y[0]:=0; x[0]:=0; x[1]:=1;
backtrace(2,1);
result;
end.