资源描述：
《c经典算法与分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、C经典算法与分析卡车史新问题（第二届选拔赛笫三题，即设备更新问题）【试题】某人购置了-•辆新卡车，从事个体运输业务.给定以下各有关数据：R[t],t=l,2,・・・，k,表示已使用过t年的卡车，再工作一年所得的运费，它随t的增加而减少，k（k韭20）年后卡车已无使用价值.U[t],t=l,・・・，k,表示已使用过t年的卡车,再工作一年所需的维修费,它随t的增加而增加.C[t],t=l,2,...,k,表示已使用过t年的
2、口卡车，卖掉I口车，买进新车，所需的净费用，它随t的增加而增加.以上各数据均为实型
3、，单位为〃万元〃.设某卡车已使用过t年，①如果继续使用，则第t+1年回收额为R[t]-U[t],②如果卖掉旧车，买进新车，则第t+1年回收额为R[0]-U[0]-C[t]•该运输户从某年初购车口起，计划工作N（NU20）年，N年后不论车的状态如何，不再工作.为使这N年的总回收额最人，应在哪些年更新旧车？假定在这N年内，运输户每年只用一辆车，而且以上各种费用均不改变.输入：用文件输入己知数据，格式为：第1行：N（运输户工作年限）第2行：k（卡车最大使用年限，k壬20）第3行:R[0]R[l]...R[k
4、]第4行：U[0]U[l]...U[k]第5行：C[0]C[l]..・C[k]输出：用文本文件按以下格式输出结果：第1行：w（N年总回收额）第2-N+1行：每行输出3个数据：年序号（从1到N按升序输出）；是否更新（当年如果更新，输出1,否则输出0）;当年冋收额（N年冋收总额应等于W）.例：设给定以下数据：N=4,k二5,i:012345R[i]:876542U[i]:0.512345C[i]:0235810则正确的输岀应该是24.5107.5215.5315.5406.0【分析】这足动态规划的一个典型
5、的例题.由题意可知，用过t年的卡午,继续使用一年的收益为d[t]=R[t]-U[t],更换新车后一年的收益为e[t]=R[0]-U[0]-C[t].我们釆用倒推分析的方法.F[j,t]表示已经使用了t年的卡车，在第j年不论继续使用还是更新，到第N年为止，可能得到的最大收益.规定当j>N时，^11果在第j年更新，则收益为p=e[t]+F[j+l,叮;如果仍使用旧车，则收益为q=d[t]+F[j+l,t+1].这里,e[t]或d[t]为第j年的收益,F[j+1,1]或F[j+1,t+1]为从第j+1年到第
6、N年在不同条件下的最大收益.显然,F[j,t]=Max(p,q).这就是所需要的计算公式.在下面的程序中，数组g[j,t]用于记录使用过t年的车，在第j年的选择方案,g[j,t]=l表示更换新车,g[j,t]二0表示仍使用I口车.【参考程序】programtjcoi2_3;{WriteByLiXuewu}typearr20=array[0..20]ofreal;varrr,uu,cc,d,e:arr20;f:array[0..22,0..21]ofreal;g:array[0.•22,0・•21]of
7、integer;i,j,k,k2,n,t:integer;filel:string[20];p,q:real;text2,text3:text;procedureinit;vari:integer;beginwriteInCInputfilename:');readln(filel);assign(text2,filel);reset(text2);readln(text2,n);readln(text2,k);fori:=0tokdoread(text2,rr[i]);readln(text2);f
8、ori:=0tokdoread(text2,uu[i]);readln(text2);fori:=0tokdoread(text2,cc[i]);readln(text2);close(text2);fori:=0tokdobegind[i]:=rr[i]-uu[i];e[i]:二d[0]-cc[i];end;end;procedureresult3;vari:integer;beginwriteln(1enterfilenameforoutput/);readln(filel);assign(tex
9、t3,filel);rewrite(tcxt3);writeln(text3,f[1,1]:8:3);writein(text3,J1O',e[O]:8:2);t:=l;fori:=2tondoifg[i,t]=lthenbeginwriteln(text3,i:2/1’，e[t]:8:2);t:=lendelsebeginwritein(text3,i:2/O',d[t]:8:2);t:=t+l;end;writeln(f[1,1]:8:3);writ
