资源描述：
《【精品】c经典算法与分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、卡车更新问题（第二届选拔赛第三题，即设备更新问题）【试题】某人购置了一辆新卡车，从事个体运输业务.给定以下各有关数据：R[t],t=l,2,...,k,表示已使用过t年的卡车，再工作一年所得的运费,它随t的增加而减少，k（kW20）年后卡车已无使用价值.U[t],t二1,表示已使用过I年的卡车，再工作一年所需的维修费,它随t的增加而增加.C[t],t=l,2,...,k,表示已使用过t年的旧卡车，卖掉旧车，买进新车,所需的净费用，它随t的增加而增加.以上各数据均为实型，单位为〃万元〃.设某卡车已使用过t年，①如果继续使用，则第t+1年回收额为
2、R[t]-U[t],②如果卖掉旧车，买进新车，则第t+1年回收额为R[O]-U[O]-C[t].该运输户从某年初购车日起，计划T作N（N〈二20）年，N年后不论车的状态如何，不再工作.为使这N年的总回收额最人，应在哪些年更新旧车？假定在这N年内，运输户每年只用一辆车，而且以上各种费用均不改变.输入：用文件输入已知数据，格式为：第1行：N（运输户工作年限）第2行：k（卡车最大使用年限，kW20）第3行：R[0]R[l]...R[k]第4行:U[0]U[l]...U[k]第5行：C[0]C[l]...C[k]输出：用文木文件按以下格式输出结果：第
3、1行：W（N年总凹收额）第2-N+1行：每行输出3个数据：年序号（从1至IJN按升序输出）;是否更新（当年如果更新，输出1,否则输出0）;当年回收额（N年回收总额应等于W）.例：设给定以下数据：N二4,k二5,■1:012345R[i]：876542U[i]:0.512345C[i]:0235810则正确的输出应该是24.5107.5115.5215.5306.0【分析】这是动态规划的一个典型的例题.由题意可知，用过t年的卡车,继续使用一年的收益为d[t]=R[t]-U[t],更换新车后一年的收益为e[t]=R[O]-U[O]-C[t].我们
4、采用倒推分析的方法・F[j,t]表示已经使用了t年的卡车，在第j年不论继续使用还是更新，到第N年为止，可能得到的最人收益.规定当j>N时,F[j,t]三0・如果在第j年更新，则收益为p二e[t]+F[j+l,1];如果仍使用旧车，则收益为q二d[t]+F[j+l,1+1].这里,e[t]或d[t]为第j年的收益，F[j+1,1]或F[j+1,t+1]为从第j+1年到第N年在不同条件下的最大收益•显然,F[j,t]=Max(p,q).这就是所需要的计算公式.在下面的程序屮，数组用于记录使用过t年的车，在第j年的选择方案,g[j,t]=l表示更换
5、新车,g[j,t]=0表示仍使用旧车.【参考程序】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]ofintegcr;i,j,k,k2,n,t:integer;fi1el:string[20];p,q:real;Lext2,text3:text;procedureinit;vari:integer;beginwritcln(JInput
6、filename:');readln(filel);assign(text2,filei);reset(text2);readln(text2,n);readIn(text2,k);fori:=0tokdoread(text2,rr[i]);readln(text2);fori:=0tokdoread(text2,uu[i]);readln(text2);fori:=0tokdoread(text2,cc[i]);readln(text2);close(text2);fori:=0tokdobegind[i]:=rr[i]-uu[i];c[i
7、]:二d[0]-cc[i];end;end;procedureresult3;vari:integer;beginwritclnCenterfilenameforoutput:，)；readln(f订cl);assign(text3,fi1el);rewrite(text3);writein(text3,f[1,1]:8:3);writein(text3,*1O',e[0]:8:2);t:=1;fori:=2tondoifg[i,t]=lthenbeginwriteln(text3,i:2/1’，e[t]:8:2);t:=1endelsebe
8、ginwriteln(text3,i:2,*O',d[t]:8:2);t:二t+1;end;writein(f[1,1]:8:3);writeinC1O',e[0]
