動態(tài)規(guī)劃講解大全(含例題及答案)

1、動態(tài)規(guī)劃講解大全動態(tài)規(guī)劃(dynamicprogramming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principleofoptimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法動態(tài)規(guī)劃。1957年出版了他的名著DynamicProgramming，這是該領(lǐng)域的第一本著作。動態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面

2、得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時(shí)間無關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時(shí)間因素，把它視為多階段決策過程，也可以用動態(tài)規(guī)劃方法方便地求解。動態(tài)規(guī)劃程序設(shè)計(jì)是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的那些搜索或數(shù)值計(jì)算那樣，具有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動態(tài)規(guī)劃程序設(shè)計(jì)往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的設(shè)計(jì)方法對不同的問

3、題，有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時(shí)，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進(jìn)行分析、討論，逐漸學(xué)會并掌握這一設(shè)計(jì)方法?；灸Ｐ投嚯A段決策過程的最優(yōu)化問題。在現(xiàn)實(shí)生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過程達(dá)到最好的活動效果。當(dāng)然，各個(gè)階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展，當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策

4、序列，因而也就確定了整個(gè)過程的一條活動路線，如圖所示：(看詞條圖)這種把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。記憶化搜索給你一個(gè)數(shù)字三角形,形式如下:12 34 567 8910找出從第一層到最后一層的一條路,使得所經(jīng)過的權(quán)值之和最小或者最大.無論對與新手還是老手，這都是再熟悉不過的題了，很容易地，我們寫出狀態(tài)轉(zhuǎn)移方程：f(i,j)=ai,j+minf(i+1,j)，f(i+1,j+1)對于動態(tài)規(guī)劃算法解決這個(gè)問題，我們根據(jù)狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移方向，比較容易地寫出動態(tài)規(guī)劃的循環(huán)表示方法。但是，當(dāng)狀態(tài)和轉(zhuǎn)移非常復(fù)雜的時(shí)候，也許寫出

5、循環(huán)式的動態(tài)規(guī)劃就不是那么簡單了。解決方法：我們嘗試從正面的思路去分析問題，如上例，不難得出一個(gè)非常簡單的遞歸過程:f1:=f(i-1,j+1);f2:=f(i-1,j);iff1>f2thenf:=f1+ai,jelsef:=f2+ai,j;顯而易見，這個(gè)算法就是最簡單的搜索算法。時(shí)間復(fù)雜度為2n，明顯是會超時(shí)的。分析一下搜索的過程，實(shí)際上，很多調(diào)用都是不必要的，也就是把產(chǎn)生過的最優(yōu)狀態(tài)，又產(chǎn)生了一次。為了避免浪費(fèi)，很顯然，我們存放一個(gè)opt數(shù)組：Opti,j-每產(chǎn)生一個(gè)f(i,j)，將f(i,j)的值放入opt中，以后再次調(diào)用到f(i,j)的時(shí)候，直接從opti,j來取就可以了。于是

6、動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程被直觀地表示出來了，這樣節(jié)省了思維的難度，減少了編程的技巧，而運(yùn)行時(shí)間只是相差常數(shù)的復(fù)雜度，避免了動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移先后的問題，而且在相當(dāng)多的情況下，遞歸算法能更好地避免浪費(fèi)，在比賽中是非常實(shí)用的.狀態(tài)決策決策：當(dāng)前狀態(tài)通過決策,回到了以前狀態(tài).可見決策其實(shí)就是狀態(tài)之間的橋梁。而以前狀態(tài)也就決定了當(dāng)前狀態(tài)的情況。數(shù)字三角形的決策就是選擇相鄰的兩個(gè)以前狀態(tài)的最優(yōu)值。狀態(tài)：我們一般在動規(guī)的時(shí)候所用到的一些數(shù)組，也就是用來存儲每個(gè)狀態(tài)的最優(yōu)值的。我們就從動態(tài)規(guī)劃的要訣，也就是核心部分“狀態(tài)”開始，來逐步了解動態(tài)規(guī)劃。有時(shí)候當(dāng)前狀態(tài)確定后,以前狀態(tài)就已經(jīng)確定,則無需枚舉.動態(tài)規(guī)劃算

7、法的應(yīng)用一、動態(tài)規(guī)劃的概念近年來，涉及動態(tài)規(guī)劃的各種競賽題越來越多，每一年的NOI幾乎都至少有一道題目需要用動態(tài)規(guī)劃的方法來解決；而競賽對選手運(yùn)用動態(tài)規(guī)劃知識的要求也越來越高，已經(jīng)不再停留于簡單的遞推和建模上了。要了解動態(tài)規(guī)劃的概念，首先要知道什么是多階段決策問題。1 .多階段決策問題如果一類活動過程可以分為若干個(gè)互相聯(lián)系的階段，在每一個(gè)階段都需作出決策(采取措施)，一個(gè)階段的決策確定以后，常常影響到下一個(gè)階段的決策，從而就完全確定了一個(gè)過程的活動路線，則稱它為多階段決策問題。各個(gè)階段的決策構(gòu)成一個(gè)決策序列，稱為一個(gè)策略。每一個(gè)階段都有若干個(gè)決策可供選擇，因而就有許多策略供我們選取，對應(yīng)于一個(gè)

8、策略可以確定活動的效果，這個(gè)效果可以用數(shù)量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個(gè)最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果.2 .動態(tài)規(guī)劃問題中的術(shù)語階段：把所給求解問題的過程恰當(dāng)?shù)胤殖扇舾蓚€(gè)相互聯(lián)系的階段，以便于求解，過程不同，階段數(shù)就可能不同.描述階段的變量稱為階段變量。在多數(shù)情況下，階段變量是離散的，用k表示。止匕外，也有階段變量是連續(xù)的情形。如果過程可以在任何時(shí)刻作出決策，且在任意兩個(gè)不同的時(shí)刻之間允許有無窮多個(gè)決策時(shí)，階段變量就是連續(xù)的。在前面的例子中，第一個(gè)階段就是點(diǎn)A,而第二個(gè)階段就是點(diǎn)A到點(diǎn)B,第三個(gè)階段是點(diǎn)B到點(diǎn)C,而第四個(gè)階段是

9、點(diǎn)C到點(diǎn)Do狀態(tài)：狀態(tài)表示每個(gè)階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉(zhuǎn)移，也稱為不可控因素。在上面的例子中狀態(tài)就是某階段的出發(fā)位置，它既是該階段某路的起點(diǎn)，同時(shí)又是前一階段某支路的終點(diǎn)。在前面的例子中，第一個(gè)階段有一個(gè)狀態(tài)即A,而第二個(gè)階段有兩個(gè)狀態(tài)B1和B2,第三個(gè)階段是三個(gè)狀態(tài)C1,C2和C3,而第四個(gè)階段又是一個(gè)狀態(tài)Do過程的狀態(tài)通?？梢杂靡粋€(gè)或一組數(shù)來描述，稱為狀態(tài)變量。一般，狀態(tài)是離散的，但有時(shí)為了方便也將狀態(tài)取成連續(xù)的。當(dāng)然，在現(xiàn)實(shí)生活中，由于變量形式的限制，所有的狀態(tài)都是離散的，但從分析的觀點(diǎn)，有時(shí)將狀態(tài)作為連續(xù)的處理將會有很大的好處。止匕外，狀態(tài)可以有多個(gè)分量

10、(多維情形)，因而用向量來代表；而且在每個(gè)階段的狀態(tài)維數(shù)可以不同。當(dāng)過程按所有可能不同的方式發(fā)展時(shí)，過程各段的狀態(tài)變量將在某一確定的范圍內(nèi)取值。狀態(tài)變量取值的集合稱為狀態(tài)集合。無后效性：我們要求狀態(tài)具有下面的性質(zhì)：如果給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都確定時(shí)，整個(gè)過程也就確定了。換句話說，過程的每一次實(shí)現(xiàn)可以用一個(gè)狀態(tài)序列表示，在前面的例子中每階段的狀態(tài)是該線路的始點(diǎn)，確定了這些點(diǎn)的序列，整個(gè)線路也就完全確定。從某一階段以后的線路開始，當(dāng)這段的始點(diǎn)給定時(shí)，不受以前線路(所通過的點(diǎn))的影響。狀態(tài)的這個(gè)性質(zhì)意味著過程的歷史只能通過當(dāng)前的狀態(tài)去影

11、響它的未來的發(fā)展，這個(gè)性質(zhì)稱為無后效性。決策：一個(gè)階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個(gè)狀態(tài)的一種選擇(行動)稱為決策。在最優(yōu)控制中，也稱為控制。在許多間題中，決策可以自然而然地表示為一個(gè)數(shù)或一組數(shù)。不同的決策對應(yīng)著不同的數(shù)值。描述決策的變量稱決策變量，因狀態(tài)滿足無后效性，故在每個(gè)階段選擇決策時(shí)只需考慮當(dāng)前的狀態(tài)而無須考慮過程的歷史。決策變量的范圍稱為允許決策集合。策略：由每個(gè)階段的決策組成的序列稱為策略。對于每一個(gè)實(shí)際的多階段決策過程，可供選取的策略有一定的范圍限制，這個(gè)范圍稱為允許策略集合。允許策略集合中達(dá)到最優(yōu)效果的策略稱為最優(yōu)策略。給定k階段狀態(tài)變量x(k)的值后，如果這一階段

12、的決策變量一經(jīng)確定，第k+1階段的狀態(tài)變量x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那么可以把這一關(guān)系看成(x(k),u(k)與x(k+1)確定的對應(yīng)關(guān)系，用x(k+1)=Tk(x(k),u(k)表示。這是從k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。最優(yōu)性原理：作為整個(gè)過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成最優(yōu)子策略D也是B1到D的最短路徑一事實(shí)正是如此，因此我們認(rèn)為這個(gè)例子滿足最優(yōu)性原理的要求。(C2<C2是A到C2的最短路徑，B1<B10D,這些點(diǎn)的選擇構(gòu)成了這個(gè)例子的最優(yōu)策略，根

13、據(jù)最優(yōu)性原理，這個(gè)策略的每個(gè)子策略應(yīng)是最優(yōu)：ACC20B10最優(yōu)性原理實(shí)際上是要求問題的最優(yōu)策略的子策略也是最優(yōu)。讓我們通過對前面的例子再分析來具體說明這一點(diǎn)：從A到D,我們知道，最短路徑是A動態(tài)規(guī)劃練習(xí)題USACO2.2SubsetSums題目如下：對于從1到N的連續(xù)整集合合，能劃分成兩個(gè)子集合，且保證每個(gè)集合的數(shù)字和是相等的。舉個(gè)例子，如果N=3，對于1，2，3能劃分成兩個(gè)子集合，他們每個(gè)的所有數(shù)字和是相等的：and1,2這是唯一一種分發(fā)(交換集合位置被認(rèn)為是同一種劃分方案，因此不會增加劃分方案總數(shù))如果N=7，有四種方法能劃分集合1，2，3，4，5，6，7，每一種分發(fā)的子集合各數(shù)字和是相

14、等的:1,6,7and2,3,4,5注1+6+7=2+3+4+52,5,7and1,3,4,63,4,7and1,2,5,61,2,4,7and3,5,6給出N，你的程序應(yīng)該輸出劃分方案總數(shù)，如果不存在這樣的劃分方案，則輸出0。程序不能預(yù)存結(jié)果直接輸出。PROGRAMNAME:subsetINPUTFORMAT輸入文件只有一行，且只有一個(gè)整數(shù)NSAMPLEINPUT(filesubset.in)7OUTPUTFORMAT輸出劃分方案總數(shù)，如果不存在則輸出0。SAMPLEOUTPUT(filesubset.out)4參考程序如下：#include<fstream>usingnames

15、pacestd;constunsignedintMAX_SUM=1024;intn;unsignedlonglongintdynMAX_SUM;ifstreamfin("subset.in");ofstreamfout("subset.out");intmain()fin>>n;fin.close();ints=n*(n+1);if(s%4)fout<<0<<endl;fout.close();return;s/=4;inti,j;dyn0=1;for(i=1;i<=n;i+)for(j=s;j>=i;j-

16、)dynj+=dynj-i;fout<<(dyns/2)<<endl;fout.close();return0;USACO2.3LongestPrefix題目如下：在生物學(xué)中，一些生物的結(jié)構(gòu)是用包含其要素的大寫字母序列來表示的。生物學(xué)家對于把長的序列分解成較短的（稱之為元素的）序列很感興趣。如果一個(gè)集合P中的元素可以通過串聯(lián)（允許重復(fù)；串聯(lián)，相當(dāng)于Pascal中的“+”運(yùn)算符）組成一個(gè)序列S，那么我們認(rèn)為序列S可以分解為P中的元素。并不是所有的元素都必須出現(xiàn)。舉個(gè)例子，序列ABABACABAAB可以分解為下面集合中的元素：A,AB,BA,CA,BBC序列S的前面K個(gè)字符

17、稱作S中長度為K的前綴。設(shè)計(jì)一個(gè)程序，輸入一個(gè)元素集合以及一個(gè)大寫字母序列，計(jì)算這個(gè)序列最長的前綴的長度。PROGRAMNAME:prefixINPUTFORMAT輸入數(shù)據(jù)的開頭包括1.200個(gè)元素（長度為1.10）組成的集合，用連續(xù)的以空格分開的字符串表示。字母全部是大寫，數(shù)據(jù)可能不止一行。元素集合結(jié)束的標(biāo)志是一個(gè)只包含一個(gè)“.”的行。集合中的元素沒有重復(fù)。接著是大寫字母序列S，長度為1.200,000，用一行或者多行的字符串來表示，每行不超過76個(gè)字符。換行符并不是序列S的一部分。SAMPLEINPUT（fileprefix.in）AABBACABBCABABACABAABCOUTPUTF

18、ORMAT只有一行，輸出一個(gè)整數(shù)，表示S能夠分解成P中元素的最長前綴的長度。SAMPLEOUTPUT(fileprefix.out)11示例程序如下：#include<stdio.h>#defineMAXP200#defineMAXL10charprimMAXP+1MAXL+1;intnump;intstart200001;chardata200000;intndata;intmain(intargc,char*argv)FILE*fout,*fin;intbest;intlv,lv2,lv3;if(fin=fopen("prim.in","r&quo

19、t;)=NULL)perror("fopenfin");exit(1);if(fout=fopen("prim.out","w")=NULL)perror("fopenfout");exit(1);while(1)fscanf(fin,"%s",primnump);if(primnump0!='.')nump+;elsebreak;ndata=0;while(fscanf(fin,"%s",data+ndata)=1)ndata+=strlen(data+nd

20、ata);start0=1;best=0;for(lv=0;lv<ndata;lv+)if(startlv)best=lv;for(lv2=0;lv2<nump;lv2+)for(lv3=0;lv+lv3<ndata&&primlv2lv3&&primlv2lv3=datalv+lv3;lv3+);if(!primlv2lv3)startlv+lv3=1;if(startndata)best=ndata;fprintf(fout,"%in",best);return0;USACO3.1ScoreInflation題目如下：我

21、們試著設(shè)計(jì)我們的競賽以便人們能盡可能的多得分,這需要你的幫助。我們可以從幾個(gè)種類中選取競賽的題目,這里的一個(gè)"種類"是指一個(gè)競賽題目的集合,解決集合中的題目需要相同多的時(shí)間并且能得到相同的分?jǐn)?shù)。你的任務(wù)是寫一個(gè)程序來告訴USACO的職員,應(yīng)該從每一個(gè)種類中選取多少題目,使得解決題目的總耗時(shí)在競賽規(guī)定的時(shí)間里并且總分最大。輸入包括競賽的時(shí)間,M(1<=M<=10,000)和N,"種類"的數(shù)目1<=N<=10,000。后面的每一行將包括兩個(gè)整數(shù)來描述一個(gè)"種類":第一個(gè)整數(shù)說明解決這種題目能得的分?jǐn)?shù)(1<=p

22、oints<=10000),第二整數(shù)說明解決這種題(1<=minutes<=10000)。你的程序應(yīng)該確定我們應(yīng)該從每個(gè)"種類"中選多少道題目使得能在競賽的時(shí)間中得到最大的分?jǐn)?shù)。來自任意的"種類"的題目數(shù)目可能任何非負(fù)數(shù)(0或更多)。計(jì)算可能得到的最大分?jǐn)?shù)。PROGRAMNAME:inflateINPUTFORMAT第1行:M,N-競賽的時(shí)間和題目"種類"的數(shù)目。第2-N+1行:兩個(gè)整數(shù):每個(gè)"種類"題目的分?jǐn)?shù)和耗時(shí)。SAMPLEINPUT(fileinflate.in)3004100602501

23、201201003520OUTPUTFORMAT單獨(dú)的一行包括那個(gè)在給定的限制里可能得到的最大的分?jǐn)?shù)。SAMPLEOUTPUT(fileinflate.out)605從第2個(gè)"種類"中選兩題，第4個(gè)"種類"中選三題示例程序如下：#include<fstream.h>ifstreamfin("inflate.in");ofstreamfout("inflate.out");constshortmaxm=10010;longbestmaxm,m,n;voidmain()shorti,j,len,pts;fi

24、n>>m>>n;for(j=0;j<=m;j+)bestj=0;for(i=0;i<n;i+)fin>>pts>>len;for(j=len;j<=m;j+)if(bestj-len+pts>bestj)bestj=bestj-len+pts;fout<<bestm<<endl;/由于數(shù)組元素不減，末元素最大USACO3.3AGame題目如下：有如下一個(gè)雙人游戲:N(2<=N<=100)個(gè)正整數(shù)的序列放在一個(gè)游戲平臺上，兩人輪流從序列的兩端取數(shù)，取數(shù)后該數(shù)字被去掉并累加到本玩家的得分中，

25、當(dāng)數(shù)取盡時(shí)，游戲結(jié)束。以最終得分多者為勝。編一個(gè)執(zhí)行最優(yōu)策略的程序，最優(yōu)策略就是使自己能得到在當(dāng)前情況下最大的可能的總分的策略。你的程序要始終為第二位玩家執(zhí)行最優(yōu)策略。PROGRAMNAME:game1INPUTFORMAT第一行:正整數(shù)N,表示序列中正整數(shù)的個(gè)數(shù)。第二行至末尾:用空格分隔的N個(gè)正整數(shù)(大小為1-200)。SAMPLEINPUT(filegame1.in)6472952OUTPUTFORMAT只有一行，用空格分隔的兩個(gè)整數(shù):依次為玩家一和玩家二最終的得分。SAMPLEOUTPUT(filegame1.out)1811參考程序如下：#include<stdio.h>#

26、defineNMAX101intbestNMAX2,tNMAX;intn;voidreadx()inti,aux;freopen("game1.in","r",stdin);scanf("%d",&n);for(i=1;i<=n;i+)scanf("%d",&aux);t=ti-1+aux;fclose(stdin);inlineintmin(intx,inty)returnx>y?y:x;voidsolve()inti,l;for(l=1;l<=n;l+)for(i=1;i+l&

27、lt;=n+1;i+)bestl%2=ti+l-1-ti-1-min(besti+1(l-1)%2,best(l-1)%2);voidwritex()freopen("game1.out","w",stdout);printf("%d%dn",best1n%2,tn-best1n%2);fclose(stdout);intmain()readx();solve();writex();return0;USACO3.4RaucousRockers題目如下：你剛剛得到了流行的“破鑼搖滾”樂隊(duì)錄制的尚未發(fā)表的N(1<=N<=20)

28、首歌的版權(quán)。你打算從中精選一些歌曲，發(fā)行M(1<=M<=20)張CD。每一張CD最多可以容納T(1<=T<=20)分鐘的音樂，一首歌不能分裝在兩張CD中。不巧你是一位古典音樂迷，不懂如何判定這些歌的藝術(shù)價(jià)值。于是你決定根據(jù)以下標(biāo)準(zhǔn)進(jìn)行選擇：歌曲必須按照創(chuàng)作的時(shí)間順序在CD盤上出現(xiàn)。選中的歌曲數(shù)目盡可能地多。PROGRAMNAME:rockersINPUTFORMAT第一行：三個(gè)整數(shù)：N,T,M.第二行：N個(gè)整數(shù)，分別表示每首歌的長度，按創(chuàng)作時(shí)間順序排列。SAMPLEINPUT(filerockers.in)4524342OUTPUTFORMAT一個(gè)整數(shù)，表示可以裝進(jìn)M張

29、CD盤的樂曲的最大數(shù)目。SAMPLEOUTPUT(filerockers.out)3參考程序如下：#include<stdio.h>#defineMAX25intdpMAXMAXMAX,lengthMAX;intmain()FILE*in=fopen("rockers.in","r");FILE*out=fopen("rockers.out","w");inta,b,c,d,best,numsongs,cdlength,numcds;fscanf(in,"%d%d%d",&n

30、umsongs,&cdlength,&numcds);for(a=1;a<=numsongs;a+)fscanf(in,"%d",&lengtha);best=0;for(a=0;a<numcds;a+)for(b=0;b<=cdlength;b+)for(c=0;c<=numsongs;c+)for(d=c+1;d<=numsongs;d+)if(b+lengthd<=cdlength)if(dpac+1>dpab+lengthdd)dpab+lengthdd=dpac+1;elseif(dpac+1>

31、;dpa+1lengthdd)dpa+1lengthdd=dpac+1;if(dpac>best)best=dpac;fprintf(out,"%dn",best);return0;解決背包問題動態(tài)規(guī)劃的定義：動態(tài)規(guī)劃的基本思想是把待求解的問題分解成若干個(gè)子問題，先求解子問題，然后再從這些子問題的解得到原問題的解，其中用動態(tài)規(guī)劃分解得到的子問題往往不是互相獨(dú)立的。動態(tài)規(guī)劃在查找有很多重疊子問題的情況的最優(yōu)解時(shí)有效。它將問題重新組合成子問題。為了避免多次解決這些子問題，它們的結(jié)果都逐漸被計(jì)算并被保存，從簡單的問題直到整個(gè)問題都被解決。因此，動態(tài)規(guī)劃保存遞歸時(shí)的結(jié)果，因而

32、不會在解決同樣的問題時(shí)花費(fèi)時(shí)間。動態(tài)規(guī)劃只能應(yīng)用于有最優(yōu)子結(jié)構(gòu)的問題。最優(yōu)子結(jié)構(gòu)的意思是局部最優(yōu)解能決定全局最優(yōu)解(對有些問題這個(gè)要求并不能完全滿足，故有時(shí)需要引入一定的近似)。簡單地說，問題能夠分解成子問題來解決。求解步驟如下：1. 找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；2. 遞歸地定義最優(yōu)值；3. 以自底向上的方式計(jì)算出最優(yōu)值；4. 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。問題描述及實(shí)現(xiàn)：背包問題：解決背包問題的方法有多種，動態(tài)規(guī)劃，貪心算法，回溯法，分支定界法都能解決背包問題。其中動態(tài)規(guī)劃，回溯法，分支定界法都是解決0-1背包問題的方法。背包問題與0-1背包問題的不同點(diǎn)在于在選擇物品裝入背

33、包時(shí)，可以只選擇物品的一部分，而不一定是選擇物品的全部。在這里，我們組用的有貪心法和動態(tài)規(guī)劃法來對這個(gè)問題進(jìn)行算法的分析設(shè)計(jì)。用動態(tài)規(guī)劃的方法可以看出如果通過第n次選擇得到的是一個(gè)最優(yōu)解的話，那么第n-1次選擇的結(jié)果一定也是一個(gè)最優(yōu)解。這符合動態(tài)規(guī)劃中最優(yōu)子問題的性質(zhì)。動態(tài)規(guī)劃方法是處理分段過程最優(yōu)化一類問題極其有效的方法。在實(shí)際生活中，有一類問題的活動過程可以分成若干個(gè)階段，而且在任一階段后的行為依賴于該階段的狀態(tài)，與該階段之前的過程是如何達(dá)到這種狀態(tài)的方式無關(guān)。這類問題的解決是多階段的決策過程?？紤]用動態(tài)規(guī)劃的方法來解決，這里的：階段是：在前n件物品中，選取若干件物品放入背包中；狀態(tài)是：在前n件物品中，選取若干件物品放入所?？臻g為w的背包中的所最大價(jià)值；決策是：第n件物品放或者不放；由此可以寫出動態(tài)轉(zhuǎn)移方程：我們用fi,j表示在前i件物品中選擇若干件放在所?？臻g為j的背包里所能獲得最大價(jià)值是：fi,j=maxfi-1,j-wi+pi(j>=wi),fi-1,j。這樣，我們可以自底向上地得出在前m件物品中取出若干件放進(jìn)背包能獲得的最大價(jià)值，也就是fm,w令f(i,j)表示用前i個(gè)物體裝出重量為j的組合時(shí)的最大價(jià)值f(i,j)=maxf(i-1,j),f(i-1,j-wi)+vi,i>0,j&