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

貪心法和動(dòng)態(tài)規(guī)劃法的區(qū)別？貪婪算法是一種策略，一種思想。沒有固定的模式。比如最簡單的背包問題，如果用貪婪的思想去做，可能會(huì)有很多性價(jià)比最高、價(jià)值最高、重量最輕的方法，但是你無法保證你選擇的貪婪策略在所

貪心法和動(dòng)態(tài)規(guī)劃法的區(qū)別？

貪婪算法是一種策略，一種思想。沒有固定的模式。比如最簡單的背包問題，如果用貪婪的思想去做，可能會(huì)有很多性價(jià)比最高、價(jià)值最高、重量最輕的方法，但是你無法保證你選擇的貪婪策略在所有情況下都是絕對最優(yōu)的。動(dòng)態(tài)規(guī)劃的思想是對剩下的進(jìn)行分而治之，把一個(gè)復(fù)雜的問題一個(gè)個(gè)分解成小問題，然后從每個(gè)小問題中得到最優(yōu)解。典型的例子可以通過畫塔問題的圖來看。

動(dòng)態(tài)規(guī)劃基本原理？

動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支，是解決決策過程最優(yōu)化的過程。

20世紀(jì)50年代初，美國數(shù)學(xué)家貝爾曼等人在研究多階段決策過程的最優(yōu)化時(shí)，提出了著名的最優(yōu)化原理，從而創(chuàng)立了動(dòng)態(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃的應(yīng)用非常廣泛，包括工程技術(shù)、經(jīng)濟(jì)、工業(yè)生產(chǎn)、軍事和自動(dòng)化控制。

在背包問題、生產(chǎn)經(jīng)營問題、資金管理問題、資源分配問題、最短路徑問題、復(fù)雜系統(tǒng)可靠性問題等方面取得了顯著的成果。

動(dòng)態(tài)規(guī)劃問題為什么用逆序標(biāo)號(hào)法？

對于同一個(gè)動(dòng)態(tài)規(guī)劃問題，逆序法和序貫法的解是相同的。動(dòng)態(tài)規(guī)劃法是將一個(gè)大問題轉(zhuǎn)化為一個(gè)小問題，即重疊子問題，然后遞歸計(jì)算。不管是逆序還是逆序，問題的每一個(gè)可能的解，比如01背包問題，都要討論每一個(gè)物品是否放進(jìn)去。對于同一個(gè)問題，明顯的解決方法不會(huì)改變，否則不代表一定有錯(cuò)誤的方法。

動(dòng)態(tài)規(guī)劃問題為什么用逆序標(biāo)號(hào)法？

標(biāo)號(hào)法是一種優(yōu)化算法，主要用于求解圖的最短路徑問題。可以說是動(dòng)態(tài)規(guī)劃，采用前推的方法，對圖的每條邊檢測一次，不需要反復(fù)回溯搜索。

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

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

為了設(shè)計(jì)標(biāo)準(zhǔn)的動(dòng)態(tài)編程算法，通常可以采取以下步驟：

劃分階段：

根據(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)系。狀態(tài)轉(zhuǎn)換是根據(jù)前一階段的狀態(tài)和決策導(dǎo)出當(dāng)前階段的狀態(tài)。因此，如果我們做一個(gè)決定，狀態(tài)轉(zhuǎn)移方程就會(huì)被寫出來。但實(shí)際上我們往往反過來做，根據(jù)相鄰兩段的狀態(tài)關(guān)系來做決策。

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

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

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

不懂也沒關(guān)系。多做幾道題，過段時(shí)間自然就知道了。

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

數(shù)字三角問題

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

38

810

2774

45265

假設(shè)一個(gè)三角形中的行數(shù)100，編程一條從頂層到底層的路徑，使沿路徑傳遞的數(shù)之和最大，文件sum.out輸出最大值。

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

分析：

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

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

假設(shè)用a[i，j]表示三角形第I行的第j個(gè)數(shù)，用p[i，j]表示從最頂層到數(shù)a[i，j]的最佳路徑的個(gè)數(shù)之和(通過該路徑的個(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]}

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

或者

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

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

p[n 1，j]=0(1jn 1)

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

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