卡车更新问题(即设备更新问题)

卡车更新问题

 (第二届选拔赛第三题，即设备更新问题)

   【试题】 某人购置了一辆新卡车, 从事个体运输业务. 给定以下各有关数据:   

    R[t], t=1,2,...,k, 表示已使用过 t 年的卡车, 再工作一年所得的运费, 它 随 t 的增加而减少, k (k≤20) 年后卡车已无使用价值.

    U[t], t=1,...,k, 表示已使用过 t 年的卡车, 再工作一年所需的维修费, 它 随 t 的增加而增加. 

    C[t], t=1,2,...,k, 表示已使用过 t 年的旧卡车, 卖掉旧车, 买进新车, 所 需的净费用, 它随 t 的增加而增加. 以上各数据均为实型, 单位为"万元".

    设某卡车已使用过 t 年,

    ① 如果继续使用, 则第 t+1 年回收额为 R[t]-U[t],

    ② 如果卖掉旧车,买进新车, 则 第 t+1 年回收额为 R[0]-U[0]-C[t] .

    该运输户从某年初购车日起,计划工作 N (N<=20) 年, N 年后不论车的状态如 何,不再工作. 为使这 N 年的总回收额最大, 应在哪些年更新旧车?  假定在这 N 年内, 运输户每年只用一辆车, 而且以上各种费用均不改变.

    输入: 用文件输入已知数据, 格式为:

      第 1 行: N (运输户工作年限)

      第 2 行: k (卡车最大使用年限, k≤20 )

      第 3 行: R[0] R[1] ... R[k]

      第 4 行: U[0] U[1] ... U[k]

      第 5 行: C[0] C[1] ... C[k]

    输出: 用文本文件按以下格式输出结果:

      第 1 行: W ( N 年总回收额 )

      第 2--N+1 行: 每行输出 3 个数据:

         年序号     ( 从 1 到 N 按升序输出 );

         是否更新   ( 当年如果更新,输出 1, 否则输出 0);

         当年回收额 ( N 年回收总额应等于 W ).

    例: 设给定以下数据:

      N=4,  k=5,

         i:   0    1    2    3    4    5

      R[i]:   8    7    6    5    4    2

      U[i]:  0.5   1    2    3    4    5

      C[i]:   0    2    3    5    8   10

    则正确的输出应该是

      24.5

      1    0   7.5

      2    1   5.5

      3    1   5.5

      4    0   6.0

【分析】这是动态规划的一个典型的例题.由题意可知,用过t年的卡车,继续使用一年的收益为d[t]=R[t]-U[t],更换新车后一年的收益为e[t]=R[0]-U[0]-C[t]. 我们采用倒推分析的方法.F[j,t]表示已经使用了t年的卡车, 在第j年不论继续使用还是更新,到第N年为止,可能得到的最大收益. 规定当j>N时, F[j,t]≡0. 如果在第j年更新,则收益为p=e[t]+F[j+1,1]; 如果仍使用旧车,则收益为 q=d[t]+F[j+1,t+1]. 这里,e[t]或d[t]为第j年的收益, F[j+1,1]或F[j+1,t+1]为从第j+1年到第N年在不同条件下的最大收益.显然,F[j,t]=Max(p,q).这就是所需要的计算公式.

   在下面的程序中,数组g[j,t]用于记录使用过t年的车,在第j年的选择方案,g[j,t]=1表示更换新车,g[j,t]=0表示仍使用旧车.

【参考程序】

program tjcoi2_3; { Write By Li Xuewu }

  type arr20=array[0..20] of real;

  var rr,uu,cc,d,e:arr20;

      f:array [0..22,0..21] of real;

      g:array [0..22,0..21] of integer;

      i,j,k,k2,n,t:integer;

      file1:string[20];

      p,q:real;

      text2,text3:text;

procedure init;

  var i:integer;

  begin

    writeln('Input filename:');

    readln(file1);

    assign(text2,file1);  reset(text2);

    readln(text2,n);    readln(text2,k);

    for i:=0 to k do read(text2,rr[i]);  readln(text2);

    for i:=0 to k do read(text2,uu[i]);  readln(text2);

    for i:=0 to k do read(text2,cc[i]);  readln(text2);

    close(text2);

    for i:=0 to k do

      begin d[i]:=rr[i]-uu[i];  e[i]:=d[0]-cc[i];  end;

  end;

procedure result3;

  var i:integer;

  begin

    writeln('enter filename for output:');

    readln(file1);

    assign(text3,file1);    rewrite(text3);

    writeln(text3,f[1,1]:8:3);

    writeln(text3,' 1  0', e[0]:8:2); t:=1;

    for i:=2 to n do

      if g[i,t]=1 then

        begin writeln(text3,i:2,'  1',e[t]:8:2); t:=1 end

      else

        begin  writeln(text3,i:2,'  0',d[t]:8:2); t:=t+1;  end ;

    writeln(f[1,1]:8:3);

    writeln(' 1  0',e[0]:8:2);  t:=1;

    for i:=2 to n do

      if g[i,t]=1 then

        begin writeln(i:2,'  1',e[t]:8:2); t:=1 end

      else

        begin  writeln(i:2,'  0',d[t]:8:2); t:=t+1;  end ;

    close(text3);

  end;

begin {main}

  init;

  for i:=0 to n do

    for j:=0 to k do  g[i,j]:=1;

  for i:=0 to k do  f[n+1,i]:=0;

  for i:=1 to n+1 do f[i,k+1]:=-100;

  for j:=n downto 2 do

    begin

      k2:=k;

      if j<k then k2:=j-1;

      for t:=1 to k2 do

        begin

          p:=e[t]+f[j+1,1];  q:=d[t]+f[j+1,t+1];

          f[j,t]:=p;   g[j,t]:=1;

          if q>p then

            begin g[j,t]:=0;  f[j,t]:=q;  end;

        end;

    end;

  f[1,1]:=d[0]+f[2,1];

  result3;

end.