動(dòng)態(tài)規(guī)劃總結(jié)和習(xí)題

1、動(dòng)態(tài)規(guī)劃總結(jié)和習(xí)題動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問(wèn)題實(shí)例分解為更小的、相似的子問(wèn)題，并存儲(chǔ)子問(wèn)題的解而避免計(jì)算重復(fù)的子問(wèn)題，以解決最優(yōu)化問(wèn)題的算法策略。由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問(wèn)題實(shí)例歸納為更小的、相似的子問(wèn)題，并通過(guò)求解子問(wèn)題產(chǎn)生一個(gè)全局最優(yōu)解。貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問(wèn)題。因此貪心法自頂向下，一步一步地作出貪心選擇； 而分治法中的各個(gè)子問(wèn)題是獨(dú)立的（即不包含公共的子問(wèn)題），因此一旦遞歸地求出各子問(wèn)題的解后，便可自下而上地將子問(wèn)題的解合并成問(wèn)題的解。不足之處：如果當(dāng)前選擇可能要依賴子問(wèn)

2、題的解時(shí)，則難以通過(guò)局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題。 解決上述問(wèn)題的辦法是利用動(dòng)態(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃方法主要應(yīng)用于最優(yōu)化問(wèn)題，這類問(wèn)題會(huì)有多種可能的解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)（最大或最小）值的解。若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過(guò)程中，該方法也是通過(guò)求解局部子問(wèn)題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同的是，動(dòng)態(tài)規(guī)劃允許這些子問(wèn)題不獨(dú)立，（亦即各子問(wèn)題可包含公共的子問(wèn)題）也允許其通過(guò)自身子問(wèn)題的解作出選擇，該方法對(duì)每一個(gè)子問(wèn)題只解一次，并將結(jié)果保存起來(lái)，避免每次碰到時(shí)都要重復(fù)計(jì)算。W

3、先生每天駕車去公司上班。W先生的住所位于A，公司位于F，圖中的直線段代表公路，交叉點(diǎn)代表路口，直線段上的數(shù)字代表兩路口之間的平均行駛時(shí)間?，F(xiàn)在W先生的問(wèn)題是要確定一條最省時(shí)的上班路線。習(xí)題12022-4-4第6章 動(dòng)態(tài)規(guī)劃法Page 5習(xí)題2用動(dòng)態(tài)規(guī)劃算法求解下面的組合優(yōu)化問(wèn)題： max g1(x1)+g2(x2)+g3(x3) x1+x2+x3=3 x1,x2,x3為非負(fù)整數(shù)其中g(shù)1(x)、g2(x)、g3(x)的值在下表中x xg g1 1(x)(x)g g2 2(x)(x)g g3 3(x)(x)02581410132716173112022習(xí)題3設(shè)有n種不同面值的硬幣，第i種硬幣的幣值

4、是vi（其中v1=1），重量是wi?，F(xiàn)在購(gòu)買總價(jià)值為y的某些商品，需要用這些硬幣付款，如果每種錢幣使用的個(gè)數(shù)不限，問(wèn)如何選擇付款的方法使得付出錢幣的總重量最輕？1、用合適的數(shù)學(xué)模型描述問(wèn)題2、使用以下的輸入實(shí)例求解問(wèn)題 1 2 3 4vi 1 4 6 8wi 1 2 4 6 y=11問(wèn)題描述：在數(shù)字序列問(wèn)題描述：在數(shù)字序列A=a1, a2, , an中按遞增中按遞增下標(biāo)序列下標(biāo)序列(i1, i2, ik)（1i1 i2 ikn）順序選）順序選出一個(gè)子序列出一個(gè)子序列B，如果子序列，如果子序列B中的數(shù)字都是嚴(yán)格中的數(shù)字都是嚴(yán)格遞增的，則子序列遞增的，則子序列B稱為序列稱為序列A的遞增子序列。最的

5、遞增子序列。最長(zhǎng)遞增子序列問(wèn)題就是要找出序列長(zhǎng)遞增子序列問(wèn)題就是要找出序列A的一個(gè)最長(zhǎng)的一個(gè)最長(zhǎng)的遞增子序列。的遞增子序列。最最長(zhǎng)遞增子序列問(wèn)題長(zhǎng)遞增子序列問(wèn)題 2022-4-4第6章 動(dòng)態(tài)規(guī)劃法Page 8最長(zhǎng)遞增子序列問(wèn)題最長(zhǎng)遞增子序列問(wèn)題想法想法設(shè)序列設(shè)序列A=a1, a2, , an最長(zhǎng)遞增子序列是最長(zhǎng)遞增子序列是B=b1, b2, bm最長(zhǎng)遞增子序列問(wèn)題滿足最優(yōu)性原理。最長(zhǎng)遞增子序列問(wèn)題滿足最優(yōu)性原理。 設(shè)設(shè)L(n)為數(shù)字序列為數(shù)字序列A=a1, a2, , an的最長(zhǎng)遞增子的最長(zhǎng)遞增子序列的長(zhǎng)度，顯然，初始子問(wèn)題是序列的長(zhǎng)度，顯然，初始子問(wèn)題是a1，即，即L(1)=1。考慮原問(wèn)題的

6、一部分，設(shè)考慮原問(wèn)題的一部分，設(shè)L(i)為子序列為子序列A=a1, a2, , ai的最長(zhǎng)遞增子序列的長(zhǎng)度，則滿足如下的最長(zhǎng)遞增子序列的長(zhǎng)度，則滿足如下遞推式：遞推式： 1 i = 1或不存在或不存在ajai（1ji）maxL(j) + 1 對(duì)于所有的對(duì)于所有的ajai（1ji）L(i) =2022-4-4第6章 動(dòng)態(tài)規(guī)劃法Page 9于序列于序列A=5, 2, 8, 6, 3, 6, 9, 7，用動(dòng)態(tài)規(guī)劃法求，用動(dòng)態(tài)規(guī)劃法求解最長(zhǎng)遞增子序列。解最長(zhǎng)遞增子序列。首先計(jì)算初始子問(wèn)題，可以直接獲得：首先計(jì)算初始子問(wèn)題，可以直接獲得：L(1)=1(5)然后依次求解下一個(gè)階段的子問(wèn)題，有：然后依次求解

7、下一個(gè)階段的子問(wèn)題，有：L(2)=1(2)L(3)=maxL(1)+1, L(2)+1=2(5, 8, 2, 8)L(4)= maxL(1)+1, L(2)+1=2(5, 6, 2, 6)L(5)=L(2)+1=2(2, 3)L(6)=maxL(1)+1, L(2)+1, L(5)+1)=3(2, 3, 6)L(7)=maxL(1)+1, L(2)+1, L(3)+1, L(4)+1, L(5)+1, L(6)+1=4(2, 3, 6, 9)L(8)=maxL(1)+1, L(2)+1, L(4)+1, L(5)+1, L(6)+1=4(2, 3, 6, 7)序列序列A的最長(zhǎng)遞增子序列的長(zhǎng)度為的最長(zhǎng)遞增子序列的長(zhǎng)度為4，有兩個(gè)最長(zhǎng)遞增子序列，分別是，有兩個(gè)最長(zhǎng)遞增子序列，分別是2, 3, 6, 9和和2, 3, 6, 7)。最長(zhǎng)遞增子序列問(wèn)題最長(zhǎng)遞增子序列問(wèn)題實(shí)例實(shí)例2022-4-4第6章 動(dòng)態(tài)規(guī)劃法Page 10序號(hào)12345678序列元素52