[工學(xué)]動態(tài)規(guī)劃題(參考版)
2025-01-22 02:51本頁面
【正文】 輸出：一個整數(shù)，最大學(xué)分數(shù)。 以下有m行表示課程，課程號依次為1,2,……,m。輸入：第一行兩個數(shù)m,n分別表示選課程總數(shù)和學(xué)生可選課程總數(shù) 1=m100，1=n=m學(xué)生修完一個課程就能獲得相應(yīng)的學(xué)分。問如何將m（1=m=20）個加號插入，使表達式值最小。f1(3)+g2(0)所以，f2(3)=max{f1(0)+g2(3),f1(1)+g2(2),f1(2)+g2(1),f1(3)+g2(0)}也就是，第一階段要事先把第二階段所要用的所有可能算出來，在計算第二階段時就可以直接引用第一階段的結(jié)果。31f1(1)+g2(2)13利潤項目1的資源 f2(0)、f2(1)——分別表示第二階段，在獲得資源為0、1時所取得的最大利潤；而第二階段與第一階段是如何聯(lián)系的？如f2(3)——表示資源3分配給前兩個項目取得最大的利潤。 f1(0)、f1(1)——分別表示第一階段，在獲得資源為0、1時所取得的最大利潤；第二階段，就是求出前二個項目在獲得所有不同資源情況下的最大利潤，例如如，第一階段，就是求出前一個項目在獲得所有不同資源情況下的最大利潤，例如 fk(n)=max{gk(x)+fk2(ax)} maxZ=g1(x1)+g2(x2)+……+gn(xn))表示可通過某決策到達(x1,x2)的所有點 *************************************************************************資源分配問題問題描述：設(shè)有資源a分配給n個項目，gr(x)為將數(shù)量為x的資源分配給項目i所能得到的利潤，i=1,2,3,……,n。)+map(x1,y1)＋map(x2,y2)｜x1x2} (x139。)+map(x1,y1)｜x1=x2，f(k1,x139。狀態(tài)轉(zhuǎn)移方程： 設(shè)map(x,y)為方格圖，f(k,x1,x2)表示第k個階段走到(x1,x2)狀態(tài)的最大和 f(0,1,1)＝map(x1,1+1x1) 即map(1,1) f(k,x1,x2)=max{f(k1,x139。決策：若用0,1分別表示向下或向右走，則每個狀態(tài)的可能決策有四種：(1,1),(0,0),(1,0),(0,1)。 由于在第k階段的任何兩個點的x,y坐標是有關(guān)系的：k+1=x+y。(2,1),(1,2)。如：第一階段，共一個狀態(tài)：(1,1),(1,1)；第二階段，(1,2),(1,2)。但，有兩條線路，故每一階段的狀態(tài)都會復(fù)雜一些。兩條路線同時進行的動態(tài)規(guī)劃中，狀態(tài)和決策以及狀態(tài)轉(zhuǎn)方程移要復(fù)雜一些。這時依然按照行走的步數(shù)來分類?，F(xiàn)考慮走兩次。決策：在每個位置有可能有兩個或一個決策可選擇，即向下或向右走（當然不能出界）。根據(jù)走的步數(shù)來分階段階段：階段1，在位置(1,1)，階段2，位置可能有兩個(1,2)，(2,1)，等。輸出：一個整數(shù)，表示兩條路徑上取得的最大的和。輸入：第一行只有一個數(shù)n（表示n*n)的方格圖，接下來每行有三個整數(shù)，前兩個整數(shù)表示方格的行和列，第三個數(shù)表示該方格放的數(shù)。0某人從左上角的A點出發(fā)，可以向下走，也可以向右走，直到達右下角的B點。00000014000004021001400000060000000 最后的結(jié)果就是：val[1]^[i,j]={i到k的通路新增q條線路的最短時間＋k到j(luò)的通路新增1q條線路的最短時間}中最優(yōu)值；*************************************************************************方格取數(shù)——多進程的動態(tài)規(guī)劃問題描述：設(shè)有n*n的方格圖（n8），我們將其中的某些方格中填入正整數(shù)，而其他的方格中則放入數(shù)字0，如下圖的樣例。 begin對val[0]運用ＦＬＯＹＤ算法，即可求出不加開線路，任何兩結(jié)點的最短旅行時間。val[0..10]是有10個map單元的數(shù)組，val[0]存儲為不加開任何線路任何兩結(jié)點的最短旅行時間，val[p]存儲加開p條線路任何兩結(jié)點的最短旅行時間。過程詳解：設(shè)map為鄰接表，鄰接表中的0表示沒有通路。而第二層次是以“允許k為中間結(jié)點”(0=k=n)為階段進行動態(tài)規(guī)劃，比如求解“允許３為中間結(jié)點”時，就要已完成“允許２為中間結(jié)點”的問題。狀態(tài)移方程：可參考以上的分析。問題“在道路ab上增加m條線路”的最優(yōu)解取決于以上兩個問題的最優(yōu)組合。狀態(tài)：在每一階段，任何兩個街區(qū)加開g(1≤g≤m)條線路的后的最短旅行時間，即共n*n個狀態(tài)。第1階段就是只加開一條線路的情況，依此類推。以加開的公交線路數(shù)為階段。如加開兩條線路，1到5的時間最短是22分鐘，加開線路是13，35。從1到5的最短路線為135用時44分鐘
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1