lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>第 2--N+1 行: 每行輸出3 個數據:<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>年序號<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp; </span>( 從 1到 N 按升序輸出 );<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>是否更新<span style="mso-spacerun: yes">&nbsp;&nbsp; </span>( 當年如果更新,輸出 1, 否則輸出0); <o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>當年回收額 ( N 年回收總額應等于 W ).<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>例: 設給定以下數據:<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>N=4,<spanstyle="mso-spacerun: yes">&nbsp; </span>k=5,<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>i:<span style="mso-spacerun: yes">&nbsp;&nbsp; </span>0<spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>1<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>2<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>3<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>4<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>5 <o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>R[i]:<spanstyle="mso-spacerun: yes">&nbsp;&nbsp; </span>8<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>7<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>6<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>5<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>4<span style="mso-spacerun: yes">&nbsp; </span><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;</span>2<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>U[i]:<spanstyle="mso-spacerun: yes">&nbsp; </span>0.5<span style="mso-spacerun:yes">&nbsp;&nbsp; </span>1<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;</span>2<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>3<spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>4<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>5 <o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>C[i]:<spanstyle="mso-spacerun: yes">&nbsp;&nbsp; </span>0<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>2<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>3<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>5<span style="mso-spacerun:yes">&nbsp;&nbsp;&nbsp; </span>8<span style="mso-spacerun: yes">&nbsp;&nbsp;</span>10<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>則正確的輸出應該是<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>24.5<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>1<spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>0<span style="mso-spacerun:yes">&nbsp;&nbsp; </span>7.5<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>2<spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>1<span style="mso-spacerun:yes">&nbsp;&nbsp; </span>5.5<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>3<spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>1<span style="mso-spacerun:yes">&nbsp;&nbsp; </span>5.5<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>4<spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>0<span style="mso-spacerun:yes">&nbsp;&nbsp; </span>6.0<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanstyle='font-size:12.0pt;mso-bidi-font-size:10.0pt'>【分析】這是動態規劃的一個典型的例題<spanlang=EN-US>.由題意可知,用過t年的卡車,繼續使用一年的收益為d[t]=R[t]-U[t],更換新車后一年的收益為e[t]=R[0]-U[0]-C[t].我們采用倒推分析的方法.F[j,t]表示已經使用了t年的卡車, 在第j年不論繼續使用還是更新,到第N年為止,可能得到的最大收益. 規定當j&gt;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).這就是所需要的計算公式.<o:p></o:p></span></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp; </span>在下面的程序中,數組g[j,t]用于記錄使用過t年的車,在第j年的選擇方案,g[j,t]=1表示更換新車,g[j,t]=0表示仍使用舊車.<o:p></o:p></span></p><p class=MsoPlainText style='line-height:20.0pt;mso-line-height-rule:exactly'><spanstyle='font-size:12.0pt;mso-bidi-font-size:10.0pt'>【參考程序】<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>program tjcoi2_3;{ Write By Li Xuewu }<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp; </span>type arr20=array[0..20] of real;<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp; </span>var rr,uu,cc,d,e:arr20;<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>f:array[0..22,0..21] of real;<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>g:array[0..22,0..21] of integer;<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>i,j,k,k2,n,t:integer;<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>file1:string[20];<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>p,q:real;<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>text2,text3:text;<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>procedure init;<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp; </span>var i:integer;<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp; </span>begin<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>writeln('Input filename:');<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>readln(file1);<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>assign(text2,file1);<spanstyle="mso-spacerun: yes">&nbsp; </span>reset(text2);<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>readln(text2,n);<spanstyle="mso-spacerun: yes">&nbsp;&nbsp; </span><span style="mso-spacerun:yes">&nbsp;</span>readln(text2,k);<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>for i:=0 to k doread(text2,rr[i]);<span style="mso-spacerun: yes">&nbsp; </span>readln(text2);<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>for i:=0 to k doread(text2,uu[i]);<span style="mso-spacerun: yes">&nbsp; </span>readln(text2);<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>for i:=0 to k doread(text2,cc[i]);<span style="mso-spacerun: yes">&nbsp; </span>readln(text2);<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>close(text2);<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>for i:=0 to k do<o:p></o:p></span></p><p class=MsoPlainText style='line-height:16.0pt;mso-line-height-rule:exactly'><spanlang=EN-US style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><spanstyle="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begind[i]:=rr[i]-uu[i]; <span style="mso-spacerun:yes">&nbsp;</span>e[i]:=d[0]-cc[i];<span style="mso-spacerun: yes">&nbsp;</span>end;<o:p></o:p></span></p>