如何寫動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程？利用動(dòng)態(tài)規(guī)劃方法解決問題的步驟設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法，通常按以下步驟進(jìn)行:階段:根據(jù)問題的時(shí)間或空間特征，將問題分為幾個(gè)階段。注意，這些階段必須是有序的或可排序的(即沒

如何寫動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移方程？

利用動(dòng)態(tài)規(guī)劃方法解決問題的步驟

設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法，通常按以下步驟進(jìn)行:

階段:

根據(jù)問題的時(shí)間或空間特征，將問題分為幾個(gè)階段。注意，這些階段必須是有序的或可排序的(即沒有后退)，否則動(dòng)態(tài)規(guī)劃無法解決問題。

選擇狀態(tài):

問題發(fā)展到各個(gè)階段的各種客觀情況，用不同的狀態(tài)表現(xiàn)出來。當(dāng)然，狀態(tài)的選擇要滿足無后效的要求。

確定決策并寫出狀態(tài)轉(zhuǎn)換方程:

之所以把這兩個(gè)步驟放在一起，是因?yàn)闆Q策和狀態(tài)轉(zhuǎn)換之間有著天然的聯(lián)系，就是根據(jù)前一階段的狀態(tài)和決策推導(dǎo)出本階段的狀態(tài)。所以，如果我們做一個(gè)決定，狀態(tài)轉(zhuǎn)移方程就會(huì)被寫出來。但實(shí)際上我們經(jīng)常反過來做，根據(jù)相鄰兩段的狀態(tài)關(guān)系來做決定。

寫出編程方程(包括邊界條件):

動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的一般形式表達(dá)式。一般來說，只要確定了階段、狀態(tài)、決策、狀態(tài)轉(zhuǎn)換，這一步就比較簡(jiǎn)單。

這是我的信息。先看看吧。我不 不太懂無后效動(dòng)態(tài)規(guī)劃的理論，但大意是根據(jù)你劃分的階段，當(dāng)前階段的選擇不會(huì)影響后面的階段。

它不 如果你不在乎。;我不明白。多做幾道題，過段時(shí)間自然就知道了。

當(dāng)然，學(xué)習(xí)DP要從簡(jiǎn)單到難。我先看了數(shù)字三角之類的，然后學(xué)了背包九講。你也可以試試。

數(shù)字三角問題

下圖顯示了一個(gè)數(shù)字三角形。數(shù)字三角形中的數(shù)字是不超過100的整數(shù)?，F(xiàn)在規(guī)定從上到下走，每一步都可以沿著左對(duì)角線或者右對(duì)角線走下去。

38

810

2774

45265

假設(shè)三角形行數(shù)小于等于100，編程求解一條從頂層到底層的路徑，使得沿著這條路徑傳遞的數(shù)之和最大，文件sum.out輸出最大值。

輸入數(shù)據(jù):數(shù)據(jù)是從一個(gè)文件中輸入的，文件的第一行是三角形的行數(shù)n。接下來的n行是從上到下每一層的數(shù)字。

分析:

如果從上到下的某個(gè)地方找到了一條最優(yōu)路徑，那么對(duì)于路徑上的每個(gè)中間點(diǎn)，這條路徑從上到下經(jīng)過的數(shù)字之和也是最大的。因此，該問題是一個(gè)典型的多階段決策優(yōu)化問題。算法設(shè)計(jì)和分析如下:

采用動(dòng)態(tài)規(guī)劃中的正向解法。如果行數(shù)為n，則該問題可視為n-1階段的決策問題。從起點(diǎn)出發(fā)，從每個(gè)決策點(diǎn)到起點(diǎn)的最佳路徑處于第一階段，第二階段...正向?qū)ふ襫-1階段，最終找到從起點(diǎn)到終點(diǎn)的最佳路徑。當(dāng)我們實(shí)現(xiàn)程序時(shí)，我們可以這樣設(shè)計(jì)它:

假設(shè)用a[i，j]表示三角形第I行中的第j個(gè)數(shù)用p[i，j]表示為從頂點(diǎn)到a[i，j]的最佳路徑的個(gè)數(shù)之和(該路徑經(jīng)過的個(gè)數(shù)之和最大)，易得問題的動(dòng)態(tài)轉(zhuǎn)移方程為:

p[0，0]0

p[i，j]max{p[i-1，j] a[i，j]，p[i-1，j-1] a[i，j]}

(1≤j≤i≤n，其中n為總行數(shù))，則max{p[n，j]}1≤j≤n為問題的解。

或者

采用動(dòng)態(tài)規(guī)劃中的逆解法。

假設(shè)用a[i，j]表示三角形第I行中的第j個(gè)數(shù)，用p[i，j]表示從底部到a[i，j]的最佳路徑的個(gè)數(shù)之和(該路徑經(jīng)過的個(gè)數(shù)之和最大)，則易得問題的動(dòng)態(tài)轉(zhuǎn)移方程為:

p[n 1，j]0(1≤j≤n 1)

p[i，j]max{p[i 1，j] a[i，j]，p[i 1，j 1] a[i，j]}

(1≤j≤i≤n，其中n為總行數(shù))，p[1，1]為問題的解。

excel規(guī)劃求解找不到最優(yōu)解？

這要看你的報(bào)表是從考勤機(jī)導(dǎo)入的還是考勤軟件導(dǎo)入的。如果考勤機(jī)的u盤下載了dat文件，要把考勤文件導(dǎo)入到考勤軟件中，然后導(dǎo)出到報(bào)表中。