不是VIP会员,不能显示答案

题目解答

题目:
(连续邮资问题)某国发行了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.
考点:
分析:
解答:
评论:
老师: