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

1、動態(tài)規(guī)劃講解大全動態(tài)規(guī)劃(dynamic programming)是運籌學(xué)的一個分支,是求解決策過程(decision process) 最優(yōu)化的數(shù)學(xué)方法.20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程 (mWtistepdecision process)的優(yōu)化問題時,提出了著名的最優(yōu)化原理 (principle of optimality) ,把多階段過程轉(zhuǎn)化為一系列單階段問題,逐個求解,創(chuàng)立了解決這類過程優(yōu)化問題的新方法一一動態(tài)規(guī)劃.1957年出版了他的名著 Dynamic Programming ,這是該領(lǐng)域的第一本著作.動態(tài)規(guī)劃問世以來,在經(jīng)濟(jì)治理、生產(chǎn)調(diào)度

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

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

4、又影響以后的開展,當(dāng)各個階段決策確定后,就組成一 個決策序列,因而也就確定了整個過程的一條活動路線,如下列圖：看詞條圖這種把一個問題看作是一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程,這種問 題就稱為多階段決策問題.記憶化搜索給你一個數(shù)字三角形,形式如下：12 34 5 67 8 9 10找出從第一層到最后一層的一條路,使得所經(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ī)劃算法解決這個問題,我們根據(jù)狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移方向,

5、比較容易地寫出動態(tài) 規(guī)劃的循環(huán)表示方法.但是,當(dāng)狀態(tài)和轉(zhuǎn)移非常復(fù)雜的時候,也許寫出循環(huán)式的動態(tài)規(guī)劃就不是那么 簡單了.解決方法:實用文檔.我們嘗試從正面的思路去分析問題,如上例,不難得出一個非常簡單的遞歸過程：f1:=f(i-1,j+1); f2:=f(i-1,j);if f1>f2 then f:=f1+ai,j else f:=f2+ai,j;顯而易見,這個算法就是最簡單的搜索算法.時間復(fù)雜度為 2n,明顯是會超時的.分析一下搜索 的過程,實際上,很多調(diào)用都是不必要的,也就是把產(chǎn)生過的最優(yōu)狀態(tài),又產(chǎn)生了一次.為了預(yù)防浪 費,很顯然,我們存放一個opt數(shù)組：Opti, j-每產(chǎn)生一個f

6、(i, j),將f(i, j)的值放入opt中,以后再次調(diào)用到f(i, j)的時候,直接從opti, j來取就可以了.于是動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程被直觀地表示出來了,這樣節(jié)省了思維的難度,減少了編程的技巧,而運行時間只是相差常數(shù)的復(fù)雜度, 預(yù)防了動態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移先后的問題,而且在相當(dāng)多的情況下,遞歸算法能更好地預(yù)防浪費,在比賽 中是非常實用的.狀態(tài)決策決策：當(dāng)前狀態(tài)通過決策,回到了以前狀態(tài).可見決策其實就是狀態(tài)之間的橋梁.而以前狀態(tài)也就決定了 當(dāng)前狀態(tài)的情況.數(shù)字三角形的決策就是選擇相鄰的兩個以前狀態(tài)的最優(yōu)值.狀態(tài)：我們一般在動規(guī)的時候所用到的一些數(shù)組,也就是用來存儲每個狀態(tài)的最優(yōu)值的.我們就從

7、動態(tài)規(guī)劃的要訣,也就是核心局部“狀態(tài)開始,來逐步了解動態(tài)規(guī)劃.有時候當(dāng)前狀態(tài)確定后,以前狀態(tài)就已經(jīng)確定,那么無需枚舉.動態(tài)規(guī)劃算法的應(yīng)用一、動態(tài)規(guī)劃的概念近年來,涉及動態(tài)規(guī)劃的各種競賽題越來越多,每一年的NOI幾乎都至少有一道題目需要用動態(tài)規(guī)劃的方法來解決；而競賽對選手運用動態(tài)規(guī)劃知識的要求也越來越高,已經(jīng)不再停留于簡單的遞推 和建模上了.要了解動態(tài)規(guī)劃的概念,首先要知道什么是多階段決策問題.1 .多階段決策問題如果一類活動過程可以分為假設(shè)干個互相聯(lián)系的階段,在每一個階段都需作出決策采取舉措,一個階段的決策確定以后,常常影響到下一個階段的決策,從而就完全確定了一個過程的活動路線, 那么稱它為多

8、階段決策問題.各個階段的決策構(gòu)成一個決策序列,稱為一個策略.每一個階段都有假設(shè)干個決策可供選擇,因 而就有許多策略供我們選取,對應(yīng)于一個策略可以確定活動的效果,這個效果可以用數(shù)量來確定.策 略不同,效果也不同,多階段決策問題,就是要在可以選擇的那些策略中間,選取一個最優(yōu)策略,使 在預(yù)定的標(biāo)準(zhǔn)下到達(dá)最好的效果 2 .動態(tài)規(guī)劃問題中的術(shù)語階段：把所給求解問題的過程恰當(dāng)?shù)胤殖杉僭O(shè)干個相互聯(lián)系的階段,以便于求解,過程不同,階段數(shù)就可能不同.描述階段的變量稱為階段變量.在多數(shù)情況下,階段變量是離散的,用k表示.此外,也有階段變量是連續(xù)的情形.如果過程可以在任何時刻作出決策,且在任意兩個不同的時刻之間 允

9、許有無窮多個決策時,階段變量就是連續(xù)的.在前面的例子中,第一個階段就是點 A,而第二個階段就是點 A到點B,第三個階段是點B到點C, 而第四個階段是點 C到點Do實用文檔. 狀態(tài)：狀態(tài)表示每個階段開始面臨的自然狀況或客觀條件,它不以人們的主觀意志為轉(zhuǎn)移,也稱為不 可控因素.在上面的例子中狀態(tài)就是某階段的出發(fā)位置,它既是該階段某路的起點,同時又是前一階 段某支路的終點.在前面的例子中,第一個階段有一個狀態(tài)即A,而第二個階段有兩個狀態(tài) B1和B2,第三個階段是三個狀態(tài)C1, C2和C3,而第四個階段又是一個狀態(tài)Do過程的狀態(tài)通?？梢杂靡粋€或一組數(shù)來描述,稱為狀態(tài)變量.一般,狀態(tài)是離散的,但有時為了

10、 方便也將狀態(tài)取成連續(xù)的.當(dāng)然,在現(xiàn)實生活中,由于變量形式的限制,所有的狀態(tài)都是離散的,但 從分析的觀點,有時將狀態(tài)作為連續(xù)的處理將會有很大的好處.止匕外,狀態(tài)可以有多個分量(多維情形),因而用向量來代表；而且在每個階段的狀態(tài)維數(shù)可以不同.當(dāng)過程按所有可能不同的方式開展時,過程各段的狀態(tài)變量將在某一確定的范圍內(nèi)取值.狀態(tài)變 量取值的集合稱為狀態(tài)集合.無后效性：我們要求狀態(tài)具有下面的性質(zhì)：如果給定某一階段的狀態(tài),那么在這一階段以后過程 的開展不受這階段以前各段狀態(tài)的影響,所有各階段都確定時,整個過程也就確定了.換句話說,過 程的每一次實現(xiàn)可以用一個狀態(tài)序列表示,在前面的例子中每階段的狀態(tài)是該線路

11、的始點,確定了這 些點的序列,整個線路也就完全確定.從某一階段以后的線路開始,當(dāng)這段的始點給定時,不受以前 線路所通過的點的影響.狀態(tài)的這個性質(zhì)意味著過程的歷史只能通過當(dāng)前的狀態(tài)去影響它的未來 的開展,這個性質(zhì)稱為無后效性.決策：一個階段的狀態(tài)給定以后,從該狀態(tài)演變到下一階段某個狀態(tài)的一種選擇行動稱為決 策.在最優(yōu)限制中,也稱為限制.在許多間題中,決策可以自然而然地表示為一個數(shù)或一組數(shù).不同 的決策對應(yīng)著不同的數(shù)值.描述決策的變量稱決策變量,因狀態(tài)滿足無后效性,故在每個階段選擇決 策時只需考慮當(dāng)前的狀態(tài)而無須考慮過程的歷史.決策變量的范圍稱為允許決策集合.策略：由每個階段的決策組成的序列稱為策

12、略.對于每一個實際的多階段決策過程,可供選取的 策略有一定的范圍限制,這個范圍稱為允許策略集合.允許策略集合中到達(dá)最優(yōu)效果的策略稱為最優(yōu) 策略.給定k階段狀態(tài)變量x(k)的值后,如果這一階段的決策變量一經(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)性原理：作為整個過程的最優(yōu)策略,它滿足：相對前面決策所形成的狀態(tài)而言,余下的子策略

13、 必然構(gòu)成“最優(yōu)子策略.D也是B1到D的最短路徑事實正是如此,因此我們認(rèn)為這個例子滿足最優(yōu)性原理的要求.C2 C2是A到C2的最短路徑,B1 B1 D,這些點的選擇構(gòu)成了這個例子的最優(yōu)策略,根據(jù)最優(yōu)性 原理,這個策略的每個子策略應(yīng)是最優(yōu)：A C2 B1最優(yōu)性原理實際上是要求問題的最優(yōu)策略的子策略也是最優(yōu).讓我們通過對前面的例子再分析來具體說明這一點：從A到D,我們知道,最短路徑是A動態(tài)規(guī)劃練習(xí)題USACO 2.2 Subset Sums題目如下：對于從1到N的連續(xù)整集合合,能劃分成兩個子集合,且保證每個集合的數(shù)字和是相等的.舉個例子,如果N=3,對于1, 2, 3能劃分成兩個子集合,他們每個的

14、所有數(shù)字和是相等的：and 1,2這是唯一一種分發(fā)交換集合位置被認(rèn)為是同一種劃分方案,因此不會增加劃分方案總數(shù)如果N=7,有四種方法能劃分集合1 , 2, 3, 4, 5, 6, 7,每一種分發(fā)的子集合各數(shù)字和是相等 的：1,6,7 and 2,3,4,5 注 1+6+7=2+3+4+52,5,7 and 1,3,4,63,4,7 and 1,2,5,61,2,4,7 and 3,5,6給出N,你的程序應(yīng)該輸出劃分方案總數(shù),如果不存在這樣的劃分方案,那么輸出 0o程序不能預(yù) 存結(jié)果直接輸出.PROGRAM NAME: subsetINPUT FORMAT輸入文件只有一行,且只有一個整數(shù)NSAM

15、PLE INPUT (file subset.in)7OUTPUT FORMAT輸出劃分方案總數(shù),如果不存在那么輸出0oSAMPLE OUTPUT (file subset.out)4參考程序如下：#include <fstream>using namespace std;const unsigned int MAX_SUM = 1024;int n;unsigned long long int dynMAX_SUM;ifstream fin ("subset.in");ofstream fout ("subset.out");int mai

16、n() fin >> n;fin.close();int s = n*(n+1);if (s % 4) fout << 0 << endl;fout.close ();return ;s /= 4;實用文檔.int i, j;dyn 0 = 1;for (i = 1; i <= n; i+)for (j = s; j >= i; j-) dynj += dynj-i;fout << (dyns/2) << endl;fout.close();return 0; USACO 2.3 Longest Prefix題目如下：在生

17、物學(xué)中,一些生物的結(jié)構(gòu)是用包含其要素的大寫字母序列來表示的.生物學(xué)家對于把長的序 列分解成較短的稱之為元素的序列很感興趣.如果一個集合P中的元素可以通過串聯(lián)允許重復(fù)；串聯(lián),相當(dāng)于 Pascal中的“+運算符 組成一個序列S ,那么我們認(rèn)為序列 S可以分解為P中的元素.并不是所有的元素都必須出現(xiàn).舉 個例子,序列ABABACABAAB!以分解為下面集合中的元素：A, AB, BA, CA, BBC序列S的前面K個字符稱作S中長度為K的前綴.設(shè)計一個程序,輸入一個元素集合以及一 個大寫字母序列,計算這個序列最長的前綴的長度.PROGRAM NAME: prefixINPUT FORMAT輸入數(shù)據(jù)的

18、開頭包括1.200 個元素長度為1.10 組成的集合,用連續(xù)的以空格分開的字符 串表示.字母全部是大寫,數(shù)據(jù)可能不止一行.元素集合結(jié)束的標(biāo)志是一個只包含一個“.的行.集合中的元素沒有重復(fù).接著是大寫字母序列S ,長度為1.200,000,用一行或者多行的字符串來表示,每行不超過76個字符.換行符并不是序列 S的一局部.SAMPLE INPUT (file prefix.in)A AB BA CA BBC .ABABACABAABCOUTPUT FORMAT只有一行,輸出一個整數(shù),表示 S能夠分解成P中元素的最長前綴的長度.SAMPLE OUTPUT (file prefix.out) 11例如

19、程序如下：#include <stdio.h>#define MAXP 200#define MAXL 10char primMAXP+1MAXL+1;int nump;int start200001;char data200000;int ndata;int main(int argc, char *argv)(FILE *fout, *fin;int best;int lv, lv2, lv3;if (fin = fopen("prim.in", "r") = NULL)(perror ("fopen fin");ex

20、it(1);if (fout = fopen("prim.out", "w") = NULL)(perror ("fopen fout");exit(1);while (1)(fscanf (fin, "%s", primnump);if (primnump0 != '.') nump+;else break;ndata = 0;while (fscanf (fin, "%s", data+ndata) = 1)ndata += strlen(data+ndata);start0

21、 = 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", be

22、st);return 0;實用文檔.USACO 3.1 Score Inflation題目如下：我們試著設(shè)計我們的競賽以便人們能盡可能的多得分,這需要你的幫助.我們可以從幾個種類中選取競賽的題目,這里的一個"種類"是指一個競賽題目的集合,解決集合中的題目需要相同多的時間并且能得到相同的分?jǐn)?shù).你的任務(wù)是寫一個程序來告訴USACO勺職員,應(yīng)該從每一個種類中選取多少題目,使得解決題目的總耗時在競賽規(guī)定的時間里并且總分最大.輸入包括競賽的時間,M(1 <= M <= 10,000) 和N,"種類"的數(shù)目1 <= N <= 10,000 .

23、后面的每一行將包括兩個整數(shù)來描述一個"種類":第一個整數(shù)說明解決這種題目能得的分?jǐn)?shù)(1 <= points <= 10000),第二整數(shù)說明解決這種題目所需的時間(1 <= minutes <= 10000).你的程序應(yīng)該確定我們應(yīng)該從每個"種類"中選多少道題目使得能在競賽的時間中得到最大的分 數(shù).來自任意的"種類"的題目數(shù)目可能任何非負(fù)數(shù)(0或更多). 計算可能得到的最大分?jǐn)?shù).PROGRAM NAME: inflate INPUT FORMAT第1行：M, N-競賽的時間和題目"種類的數(shù)目. 第2-

24、N+1行：兩個整數(shù)：每個"種類"題目的分?jǐn)?shù)和耗時.SAMPLE INPUT (file inflate.in) 300 4 100 60 250 120 120 100 35 20 OUTPUT FORMAT 單獨的一行包括那個在給定的限制里可能得到的最大的分?jǐn)?shù).SAMPLE OUTPUT (file inflate.out) 605從第2個"種類中選兩題,第4個"種類"中選三題 例如程序如下：#include <fstream.h> ifstream fin("inflate.in"); ofstream fo

25、ut("inflate.out"); const short maxm = 10010; long bestmaxm, m, n; void main() short i, j, len, pts;fin >> 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 = bes

26、tj-len + pts;由于數(shù)組元素不減,末元素最大)fout « bestm « end I; /)USACO 3.3 A Game題目如下：有如下一個雙人游戲:N(2 <= N <= 100)個正整數(shù)的序列放在一個游戲平臺上,兩人輪流從序列的 兩端取數(shù),取數(shù)后該數(shù)字被去掉并累加到本玩家的得分中,當(dāng)數(shù)取盡時,游戲結(jié)束.以最終得分多者 為勝.編一個執(zhí)行最優(yōu)策略的程序,最優(yōu)策略就是使自己能得到在當(dāng)前情況下最大的可能的總分的策略.你的程序要始終為第二位玩家執(zhí)行最優(yōu)策略.PROGRAM NAME: gamelINPUT FORMAT第一行：正整數(shù)N,表示序列中正整數(shù)

27、的個數(shù).第二行至末尾：用空格分隔的N個正整數(shù)大小為1-200.SAMPLE INPUT (file game1.in)64 7 2 95 2OUTPUT FORMAT只有一行,用空格分隔的兩個整數(shù)：依次為玩家一和玩家二最終的得分.SAMPLE OUTPUT (file gamel.out)18 11參考程序如下：#include <stdio.h>#define NMAX 101int bestNMAX2, tNMAX;int n;voidreadx () int i, aux;freopen ("game1.in", "r", stdin)

28、;scanf ("%d", &n);for (i = 1; i <= n; i+) scanf ("%d", &aux);t = ti - 1 + aux;)fclose (stdin);)inline intmin (int x, int y) return x > y ? y : x;)voidsolve () int i, l;實用文檔.for (l = 1; l <= n; l+)for (i = 1; i + l <= n + 1; i+)bestl%2 = ti + l - 1 - ti - 1 - m

29、in (besti + 1(l - 1) % 2, best(l - 1) % 2);)void writex () freopen ("game1.out", "w", stdout);printf ("%d %dn", best1n % 2, tn - best1n % 2); fclose (stdout);) int main () readx (); solve (); writex (); return 0;)實用文檔.USACO 3.4 Raucous Rockers題目如下：你剛剛得到了流行的“破鑼搖滾樂隊錄制的尚未發(fā)

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

31、rockers.in) 4 5 2 4 3 4 2OUTPUT FORMAT一個整數(shù),表示可以裝進(jìn) M張CD盤的樂曲的最大數(shù)目.SAMPLE OUTPUT (file rockers.out) 3 參考程序如下：#include <stdio.h>#define MAX 25int dpMAXMAXMAX, lengthMAX;intmain () FILE *in = fopen ("rockers.in", "r"); FILE *out = fopen ("rockers.out", "w");

32、int a, b, c, d, best, numsongs, cdlength, numcds; fscanf (in, "%d%d%d", &numsongs, &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 <= numson

33、gs; c+) for (d = c + 1; d <= numsongs; d+) if (b + lengthd <= cdlength) if (dpac + 1 > dpab + lengthdd)dpab + lengthdd = dpac + 1;else 實用文檔. if (dpac + 1 > dpa + 1lengthdd) dpa + 1lengthdd = dpac + 1;)if (dpac > best)best = dpac;)fprintf (out, "%dn", best);return 0;)實用文檔.解決背

34、包問題動態(tài)規(guī)劃的定義：動態(tài)規(guī)劃的根本思想是把待求解的問題分解成假設(shè)干個子問題,先求解子問題,然后再從這些子問題 的解得到原問題的解,其中用動態(tài)規(guī)劃分解得到的子問題往往不是互相獨立的.動態(tài)規(guī)劃在查找有很 多重疊子問題的情況的最優(yōu)解時有效.它將問題重新組合成子問題.為了預(yù)防屢次解決這些子問題, 它們的結(jié)果都逐漸被計算并被保存,從簡單的問題直到整個問題都被解決.因此,動態(tài)規(guī)劃保存遞歸 時的結(jié)果,因而不會在解決同樣的問題時花費時間.動態(tài)規(guī)劃只能應(yīng)用于有最優(yōu)子結(jié)構(gòu)的問題.最優(yōu) 子結(jié)構(gòu)的意思是局部最優(yōu)解能決定全局最優(yōu)解對有些問題這個要求并不能完全滿足,故有時需要引入一定的近似.簡單地說,問題能夠分解成子問

35、題來解決.求解步驟如下：1 .找出最優(yōu)解的性質(zhì),并刻畫其結(jié)構(gòu)特征；2 .遞歸地定義最優(yōu)值；3 .以自底向上的方式計算出最優(yōu)值；4 .根據(jù)計算最優(yōu)值時得到的信息,構(gòu)造最優(yōu)解.問題描述及實現(xiàn)：背包問題：解決背包問題的方法有多種,動態(tài)規(guī)劃,貪心算法,回溯法,分支定界法都能解決背包問題.其中動態(tài)規(guī)劃,回溯法,分支定界法都是解決0-1背包問題的方法.背包問題與0-1背包問題的不同點在于在選擇物品裝入背包時,可以只選擇物品的一局部,而不一定是選擇物品的全部.在這里, 我們組用的有貪心法和動態(tài)規(guī)劃法來對這個問題進(jìn)行算法的分析設(shè)計.用動態(tài)規(guī)劃的方法可以看出如 果通過第n次選擇得到的是一個最優(yōu)解的話,那么第 n

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