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

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

3、先生每天駕車去公司上班。W先生的住所位于A，公司位于F，圖中的直線段代表公路，交叉點(diǎn)代表路口，直線段上的數(shù)字代表兩路口之間的平均行駛時(shí)間?，F(xiàn)在W先生的問題是要確定一條最省時(shí)的上班路線。習(xí)題12022-4-8第6章 動(dòng)態(tài)規(guī)劃法Page 5習(xí)題2用動(dòng)態(tài)規(guī)劃算法求解下面的組合優(yōu)化問題： 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。現(xiàn)在購買總價(jià)值為y的某些商品，需要用這些硬幣付款，如果每種錢幣使用的個(gè)數(shù)不限，問如何選擇付款的方法使得付出錢幣的總重量最輕？1、用合適的數(shù)學(xué)模型描述問題2、使用以下的輸入實(shí)例求解問題 1 2 3 4vi 1 4 6 8wi 1 2 4 6 y=11問題描述：在數(shù)字序列問題描述：在數(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、遞增子序列。最長遞增子序列問題就是要找出序列長遞增子序列問題就是要找出序列A的一個(gè)最長的一個(gè)最長的遞增子序列。的遞增子序列。最最長遞增子序列問題長遞增子序列問題 2022-4-8第6章 動(dòng)態(tài)規(guī)劃法Page 8最長遞增子序列問題最長遞增子序列問題想法想法設(shè)序列設(shè)序列A=a1, a2, , an最長遞增子序列是最長遞增子序列是B=b1, b2, bm最長遞增子序列問題滿足最優(yōu)性原理。最長遞增子序列問題滿足最優(yōu)性原理。 設(shè)設(shè)L(n)為數(shù)字序列為數(shù)字序列A=a1, a2, , an的最長遞增子的最長遞增子序列的長度，顯然，初始子問題是序列的長度，顯然，初始子問題是a1，即，即L(1)=1。考慮原問題的

6、一部分，設(shè)考慮原問題的一部分，設(shè)L(i)為子序列為子序列A=a1, a2, , ai的最長遞增子序列的長度，則滿足如下的最長遞增子序列的長度，則滿足如下遞推式：遞推式： 1 i = 1或不存在或不存在ajai（1ji）maxL(j) + 1 對于所有的對于所有的ajai（1ji）L(i) =2022-4-8第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ī)劃法求解最長遞增子序列。解最長遞增子序列。首先計(jì)算初始子問題，可以直接獲得：首先計(jì)算初始子問題，可以直接獲得：L(1)=1(5)然后依次求解下一個(gè)階段的子問題，有：然后依次求解

7、下一個(gè)階段的子問題，有：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的最長遞增子序列的長度為的最長遞增子序列的長度為4，有兩個(gè)最長遞增子序列，分別是，有兩個(gè)最長遞增子序列，分別是2, 3, 6, 9和和2, 3, 6, 7)。最長遞增子序列問題最長遞增子序列問題實(shí)例實(shí)例2022-4-8第6章 動(dòng)態(tài)規(guī)劃法Page 10序號12345678序列元素52