[工學(xué)]動態(tài)規(guī)劃題-在線瀏覽
2025-03-08 02:51本頁面
【正文】 1 22 3 輸出例子6 33 21 22 2解法一：*************************************************************************胖子跳舞問題描述：一個胖子很喜歡玩跳舞毯，但是每次都玩的很累。上下左右一次為1，2，3，4。一只腳在原地重復(fù)踏一下耗費體力值1?！ 『苊黠@，跳舞序列是固定，可以按這個序列定義動態(tài)規(guī)劃的階段。狀態(tài)：人的兩只腳的位置就表示兩種狀態(tài)，即每一階段有兩種狀態(tài)用si[1],si[2]，如第0階段的狀態(tài)s0[1]=0,s0[2]=0。即對跳舞序列的第i+1個，可以動左或右腳去實現(xiàn)。*************************************************************************砝碼稱重問題描述：有一組砝碼，重量互不相等，分別為mmm3……mn；它們可取的最大數(shù)量分別為xxx3……xn。輸入： 第二行n個整數(shù)（中間用空格分隔），mmm3……mn，分別表示n個砝碼的重量；（1=mi=20）（1=xi=20）輸出： 僅一行，一個整數(shù)，表示利用給定的砝碼可以稱出的不同的重量數(shù)。狀態(tài)：在某個階段，以能稱出的重量為狀態(tài)。 設(shè)：f(w,i)表示在第i階段，能否稱出w的重量，能則為 true，否為false。 f(w,i)僅與第i1階段有關(guān)。狀態(tài)轉(zhuǎn)移方程：f(w,i)=f(w,i1)∨f(w1*wi,i1)∨f(w2*wi,i1)∨……∨f(wxi*wi,i1) 某城市有n(1≤n≤50)個街區(qū)，某些街區(qū)有公共汽車線路相連，如下圖，圖中邊上的數(shù)字為兩個街區(qū)間汽車的旅行時間（也就是乘客等車時間）。此主題相關(guān)圖片如下：現(xiàn)市政府要改善交通，決定加開m(1≤m≤10)條線路的公共汽車，并規(guī)定：只有已有了公共汽車線路的才能加開線路，加開一條線路后，等車時間減半，若再加開一條，等車時間再減半，依此類推。求加開哪些線路，可使街區(qū)1到n的時間最短，并輸出出加開的線路。參考FLOYD算法。階段：第0階段就是不加開任何線路的情況，即原始狀態(tài)（直接用ＦＬＯＹＤ算法就可求出任何兩點的最短旅行時間）。第m階段就是加開了m條線路的情況也就是所求。決策：在道路ab上增加g條線路可分為以下兩個問題（如果k是最短路上的一點）①在ak的道路上增加t條邊②在kb的道路上增加gt條邊k可取0到m間的任何整數(shù)。即：“在ak的道路上增加t條邊”后旅行時間和“在kb的道路上增加mt條邊”后旅行時間之和最小值。綜合，以上分析可以發(fā)現(xiàn)：上述的動態(tài)規(guī)劃，第一個層次是以“加開的公交線路數(shù)為階段”，進(jìn)行動態(tài)規(guī)劃，比如要完成加３條公交線路的任務(wù)，就要先要完成加１條和加２條線路的問題。故稱為雙重動態(tài)規(guī)劃 但決策并沒有更復(fù)雜，設(shè)現(xiàn)在要加開發(fā)公交線路數(shù)為g，允許中間結(jié)點為k，可選決策集（也就是狀態(tài)）為ak的線路上加p條線線路，kb而的線路上加gp條線路（g=p=0）。如map[i,j]=0表示i,j間沒有通路。way[0..10,1..50,1..50,1..2]記錄i到j(luò)路徑上新增p條線路的最佳方案，其中way[p,i,j,2]存儲ij的路徑的中間結(jié)點k，way[p,i,j,1]存ik的路徑上新增的線路數(shù)。求val[1]（只加開一條線路）val[1]=鄰接表（注意，鄰接表中的0表示沒有通路）； val[1]中各值減半；for k=1 to n do 列舉各個中間結(jié)點 for i=1 to n do for j=1 to n do 列舉所有的兩街區(qū)線路 if(i到k有通路and j到k有通路and ij) thenfor(列舉q的所有可能) if(Val[p]^[i,j]=0 or Val[p]^[i,j]Val[q]^[i,k]＋Val[1q]^[k,j]) then 記錄較優(yōu)值； end。0 000130000 70000000000150000000000在走過的路上，它可以取走方格中的數(shù)（取走數(shù)后，方格中的數(shù)為0），此人從A到B共兩次，試找出兩條這樣的路徑，使取得的數(shù)的和最大。一行單獨的0表示輸入結(jié)束。若只考慮走一次的情況，則是一個標(biāo)準(zhǔn)的動態(tài)規(guī)劃的過程。其中的規(guī)律是階段k，可能的位置是(x,k+1x),(k=x=1)狀態(tài)：每個階段有若干個狀態(tài)，如上所述階段k的狀態(tài)有: (x,k+1x),(k=x=1)。狀態(tài)轉(zhuǎn)移方程：位置(x,y)的狀態(tài)：S(x,y)=min{ s(x1,y), s(x,y1) }+格子(x,y)中的數(shù)。題目中是兩次分開走的，但我們可以看成兩個人同時走。這
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1