信息系統(tǒng)項(xiàng)目管理師綜合知識(shí)真題考點(diǎn)：動(dòng)態(tài)規(guī)劃

使用動(dòng)態(tài)規(guī)劃求解問題，最重要的就是確定動(dòng)態(tài)規(guī)劃三要素：

(1)問題的階段

(2)每個(gè)階段的狀態(tài)

(3)從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系。

遞推關(guān)系必須是從次小的問題開始到較大的問題之間的轉(zhuǎn)化，從這個(gè)角度來說，動(dòng)態(tài)規(guī)劃往往可以用遞歸程序來實(shí)現(xiàn)，不過因?yàn)檫f推可以充分利用前面保存的子問題的解來減少重復(fù)計(jì)算，所以對(duì)于大規(guī)模問題來說，有遞歸不可比擬的優(yōu)勢(shì)，這也是動(dòng)態(tài)規(guī)劃算法的核心之處。確定了動(dòng)態(tài)規(guī)劃的這三要素，整個(gè)求解過程就可以用一個(gè)最優(yōu)決策表來描述，最優(yōu)決策表是一個(gè)二維表，其中行表示決策的階段，列表示問題狀態(tài)，表格需要填寫的數(shù)據(jù)一般對(duì)應(yīng)此問題的在某個(gè)階段某個(gè)狀態(tài)下的最優(yōu)值(如最短路徑，最長(zhǎng)公共子序列，最大價(jià)值等)，填表的過程就是根據(jù)遞推關(guān)系，從1行1列開始，以行或者列優(yōu)先的順序，依次填寫表格，最后根據(jù)整個(gè)表格的數(shù)據(jù)通過簡(jiǎn)單的取舍或者運(yùn)算求得問題的最優(yōu)解:f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

詳見官方教材《信息系統(tǒng)項(xiàng)目管理師教程》(第3版)878-881頁

考點(diǎn)相關(guān)真題

相關(guān)閱讀：信息系統(tǒng)項(xiàng)目管理師綜合知識(shí)真題考點(diǎn)匯總