《動態(tài)規(guī)劃 算法》由會員分享，可在線閱讀，更多相關《動態(tài)規(guī)劃 算法（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、動態(tài)規(guī)劃算法介紹一一概念、意義及應用、例題(2012-05-14 21:54:37)轉載▼標簽：雜談 動態(tài)規(guī)劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最 優(yōu)化的數(shù)學方法。20世紀50年代初美國數(shù)學家R.E.Bellman等人在研究多階段決策過程 (multistep decision process)的優(yōu)化問題時，提出 了著名的最優(yōu)化原理(principle of optimality), 把多階段過程轉化為一系列單階段問題，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法 動態(tài)規(guī)劃。1957年出版了他的名著Dynamic

2、Programming,這是該領域的第一本著作。 動態(tài)規(guī)劃問世以來，在經(jīng)濟管理、生產(chǎn)調度、工程技術和最優(yōu)控制等方面得到了廣泛的 應用。例如最短路線、庫存管理、資源分配、設備更新、排序、裝載等問題，用動態(tài)規(guī)劃方 法比用其它方法求解更為方便。 雖然動態(tài)規(guī)劃主要用于求解以時間劃分階段的動態(tài)過程的優(yōu)化問題，但是一些與時間無 關的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進時間因素，把它視為多階段決策 過程，也可以用動態(tài)規(guī)劃方法方便地求解。 動態(tài)規(guī)劃程序設計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不 象前面所述的那些搜索或數(shù)值計算那樣，具有一個標準的數(shù)學表達式和明確清晰的解

3、題方 法。動態(tài)規(guī)劃程序設計往往是針對一種最優(yōu)化問題，由于各種問題的性質不同，確定最優(yōu)解 的條件也互不相同，因而動態(tài)規(guī)劃的設計方法對不同的問題，有各具特色的解題方法，而不 存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學習時，除了要對基 本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想彖力去建立模型，用創(chuàng) 造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進行分析、討論, 逐漸學會并掌握這一設計方法。 基本模型 多階段決策過程的最優(yōu)化問題。 在現(xiàn)實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的 階段，在它的每一階段都需要作

4、出決策，從而使整個過程達到最好的活動效果。當然，各個 階段決策的選取不是任意確定的，它依賴于當前面臨的狀態(tài)，又影響以后的發(fā)展，當各個階 段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線，如圖所示： (看詞條圖) 這種把一個問題看作是一個前后關聯(lián)具有鏈狀結構的多階段過程就稱為多階段決策過 程，這種問題就稱為多階段決策問題。 記憶化搜索 給你一個數(shù)字三角形，形式如下： 1 23 456 789 10 找出從第一層到最后一層的一條路，使得所經(jīng)過的權值之和最小或者最人. 無論對與新手還是老手，這都是再熟悉不過的題了，很容易地，我們寫出狀態(tài)轉移方程： f(i, j

5、)=a[i, j] + min{f(i+l, j), f(i+l, j + 1)} 對于動態(tài)規(guī)劃算法解決這個問題，我們根據(jù)狀態(tài)轉移方程和狀態(tài)轉移方向，比較容易地 寫出動態(tài)規(guī)劃的循壞表示方法。但是，當狀態(tài)和轉移非常復雜的時候，也許寫出循壞式的動 態(tài)規(guī)劃就不是那么簡單了。 解決方法： 我們嘗試從正面的思路去分析問題，如上例，不難得出一個非常簡單的遞歸過程： if fl>f2 then f:=fl+a[ij] else f:=f2+a[i,j]; 顯而易見，這個算法就是最簡單的搜索算法。時間復雜度為2n,明顯是會超時的。分 析一下搜索的過程，實際上，很多調用都是不必要的，也就是把產(chǎn)生過的最

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

7、兩個以前狀態(tài)的最優(yōu)值。 狀態(tài)： 我們一般在動規(guī)的時候所用到的一些數(shù)組，也就是用來存儲每個狀態(tài)的最優(yōu)值的。我們 就從動態(tài)規(guī)劃的要訣，也就是核心部分“狀態(tài)”開始，來逐步了解動態(tài)規(guī)劃。有時候當前狀 態(tài)確定后，以前狀態(tài)就已經(jīng)確定,則無需枚舉. 動態(tài)規(guī)劃算法的應用 一、動態(tài)規(guī)劃的概念 近年來，涉及動態(tài)規(guī)劃的各種競賽題越來越多，每一年的NOI幾乎都至少有一道題目需 要用動態(tài)規(guī)劃的方法來解決；而競賽對選手運用動態(tài)規(guī)劃知識的要求也越來越高，已經(jīng)不再 停留于簡單的遞推和建模上了。 要了解動態(tài)規(guī)劃的概念，首先要知道什么是多階段決策問題。 1. 多階段決策問題 如果一類活動過程可以分為若干個互相聯(lián)系

8、的階段，在每一個階段都需作出決策(采取 措施)，一個階段的決策確定以后，常常影響到下一個階段的決策，從而就完全確定了一個 過程的活動路線，則稱它為多階段決策問題。 各個階段的決策構成一個決策序列，稱為一個策略。每一個階段都有若干個決策可供選 擇，因而就有許多策略供我們選取，對應于一個策略可以確定活動的效果，這個效果可以用 數(shù)量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間， 選取一個最優(yōu)策略，使在預定的標準下達到最好的效果. 2. 動態(tài)規(guī)劃問題中的術語 階段：把所給求解問題的過程恰當?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便于求解，過程不 同，階段數(shù)就可能不同.描述階

9、段的變屋稱為階段變量。在多數(shù)情況卞，階段變量是離散的， 用k表示。此外，也有階段變量是連續(xù)的情形。如呆過程可以在任何時刻作出決策，且在任 意兩個不同的時刻之間允許有無窮多個決策時，階段變量就是連續(xù)的。 在前面的例子中，第一個階段就是點A,而第二個階段就是點A到點B,第三個階段是 點B到點C,而第四個階段是點C到點D。 狀態(tài)：狀態(tài)表示每個階段開始面臨的自然狀況或客觀條件，它不以人們的主觀意志為轉 移，也稱為不可控因素。在上面的例子中狀態(tài)就是某階段的出發(fā)位置，它既是該階段某路的 起點，同時又是前一階段某支路的終點。 在前面的例子中，第一個階段有一個狀態(tài)即A,而第二個階段有兩個狀態(tài)B1和B2,

10、第 三個階段是三個狀態(tài)Cl, C2和C3,而第四個階段又是一個狀態(tài)D。 過程的狀態(tài)通?？梢杂靡粋€或一組數(shù)來描述，稱為狀態(tài)變量。一般，狀態(tài)是離散的，但 有時為了方便也將狀態(tài)取成連續(xù)的。當然，在現(xiàn)實生活中，由于變量形式的限制，所有的狀 態(tài)都是離散的，但從分析的觀點，有時將狀態(tài)作為連續(xù)的處理將會有很人的好處。此外，狀 態(tài)可以有多個分量(多維情形)，因而用向量來代表；而且在每個階段的狀態(tài)維數(shù)可以不同。 當過程按所有可能不同的方式發(fā)展時，過程各段的狀態(tài)變量將在某一確定的范闈內取 值。狀態(tài)變量取值的集合稱為狀態(tài)集合。 無后效性：我們要求狀態(tài)具有下面的性質：如杲給定某一階段的狀態(tài)，則在這一階段以 后過

11、程的發(fā)展不受這階段以前各段狀態(tài)的影響,所有各階段都確定時，整個過程也就確定了。 換句話說，過程的每一次實現(xiàn)可以用一個狀態(tài)序列表示，在前面的例子中每階段的狀態(tài)是該 線路的始點，確定了這些點的序列，整個線路也就完全確定。從某一階段以后的線路開始, 當這段的始點給定時，不受以前線路(所通過的點)的影響。狀態(tài)的這個性質意味著過程的 歷史只能通過當前的狀態(tài)去影響它的未來的發(fā)展，這個性質稱為無后效性。 決策:一個階段的狀態(tài)給定以后，從該狀態(tài)演變到下一階段某個狀態(tài)的一種選擇(行動) 稱為決策。在最優(yōu)控制中，也稱為控制。在許多間題中，決策可以自然而然地表示為一個數(shù) 或一組數(shù)。不同的決策對應著不同的數(shù)值。描述

12、決策的變量稱決策變量，因狀態(tài)滿足無后效 性，故在每個階段選擇決策時只需考慮當前的狀態(tài)而無須考慮過程的歷史。 決策變量的范圍稱為允許決策集合。 策略：由每個階段的決策組成的序列稱為策略。對于每一個實際的多階段決策過程，可 供選取的策略有一定的范I韋I限制，這個范I制稱為允許策略集合。允許策略集合中達到最優(yōu)效 果的策略稱為最優(yōu)策略。 給定k階段狀態(tài)變量x(k)的值后，如果這一階段的決策變量一經(jīng)確定，第k+1階段的狀 態(tài)變量x(k+l)也就完全確定，即x(k+l)的值隨x(k)和第k階段的決策u(k)的值變化而變化, 那么可以把這一關系看成(x(k), u(k))與x(k+l)確定的對應關系，

13、用x(k+l)=Tk(x(k),u(k))表示。 這是從k階段到k+l階段的狀態(tài)轉移規(guī)律，稱為狀態(tài)轉移方程。 最優(yōu)性原理:作為整個過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余 下的子策略必然構成“最優(yōu)子策略”。 最優(yōu)性原理實際上是要求問題的最優(yōu)策略的子策略也是最優(yōu)。讓我們通過對前面的例子 再分析來具體說明這一點：從A到D,我們知道，最短路徑是A Bl C2 D,這些點的選 擇構成了這個例子的最優(yōu)策略，根據(jù)最優(yōu)性原理，這個策略的每個子策略應是最優(yōu)： A Bl C2是A到C2的最短路徑，Bl C2 D也是Bl到D的最短路徑……——爭實正是 如此，因此我們認為這個例子滿足最優(yōu)性原理的

14、要求。 動態(tài)規(guī)劃練習題 USACO 2.2 Subset Sums 題目如下： 對于從1到N的連續(xù)整集合合，能劃分成兩個子集合，且保證每個集合的數(shù)字和是相 等的。 舉個例子，如果N=3,對于{1, 2, 3}能劃分成兩個子集合，他們每個的所有數(shù)字和是相 等的： and {1,2} 這是唯一一種分發(fā)（交換集合位置被認為是同一種劃分方案，因此不會增加劃分方案總 數(shù)) 如果N=7,有四種方法能劃分集合{1, 2, 3, 4, 5, 6, 7},每一種分發(fā)的子集合各數(shù)字 和是相等的： {1,6,7} and {234,5} {注 1+6+7=2+3+4+5} {2,5,7} and

15、 {134,6} {3,4,7} and {1,2,5,6} {124,7} and {3,5,6} 給出N,你的程序應該輸出劃分方案總數(shù)，如果不存在這樣的劃分方案，則輸出0。程 序不能預存結果直接輸出。 PROGRAM NAME: subset INPUT FORMAT 輸入文件只有一行，且只有一個整數(shù)N SAMPLE INPUT (file subset.in) 7 OUTPUT FORMAT 輸出劃分方案總數(shù)，如果不存在則輸出0。 SAMPLE OUTPUT (file subset.out) 4 參考程序如下： #include usi

16、ng namespace std; const unsigned int MAX_SUM = 1024; int n; unsigned long long int dyn[MAX_SUM]; ifstream fin ("subset.in"); ofstream fout「subset.out”)； int main() { fin ? n; fin.close(); int s = n*(n+l); if (s % 4) { fout? 0 ? endl; fout.close (); return; } s/= 4; int i, j； dyn [0]

17、 = 1; for (i = 1; i <= n; i++) for (j = s; j >= i; j-) dyn[j] += dynU-i]； fout? (dyn[s]/2) ? endl; fout.close(); return 0; } USACO 2.3 Longest Prefix 題目如下： 在生物學中，一些生物的結構是用包含其要素的人寫字母序列來表示的。生物學家對于 把長的序列分解成較短的(稱之為元素的)序列很感興趣。 如果一個集合P中的元素可以通過串聯(lián)(允許重復；串聯(lián)，相當于Pascal中的“ + ” 運算符)組成一個序列S ,那么我們認為序列S可以

18、分解為P中的元素。并不是所有的 元素都必須出現(xiàn)。舉個例子，序列ABABACABAAB可以分解為下面集合中的元素： {A, AB, BA, CA, BBC} 序列S的前面K個字符稱作S中長度為K的前綴。設計一個程序，輸入一個元素集 合以及一個大寫字母序列，計算這個序列最長的前綴的長度。 PROGRAM NAME: prefix INPUT FORMAT 輸入數(shù)據(jù)的開頭包拾1..200個元素(長度為1..10 )組成的集合，用連續(xù)的以空格分 開的字符串表示。字母全部是犬寫，數(shù)據(jù)可能不止一行。元素集合結束的標志是一個只包含 一個的行。集合中的元素沒有重復。接著是大寫字母序列S ,長度為1.

19、.200Q00 , 用一行或者多行的字符串來表示，每行不超過76個字符。換行符并不是序列S的一部分。 SAMPLE INPUT (file prefix.in) A AB BA CA BBC ■ ABABACABAABC OUTPUT FORMAT 只有一行，輸出一個整數(shù)，表示s能夠分解成P中元素的最長前綴的長度。 SAMPLE OUTPUT (file prefix.out) 11 示例程序如下： #include #define MAXP 200 #define MAXL 10 char prim[MAXP+l][MAXL+l]; int n

20、ump; int start[200001]; char data[200000]; int ndata; int main(int argcz char **argv) { FILE *fout, *fin; int best; int Iv, Iv2, Iv3; if ((fin = fopen("prim.in,,/ "r")) == NULL) { perror (Hfope n fin"); exit(l); } if ((fout = fopenC'prim.out", "w")) == NULL) { perror (Hfope n foutH)；

21、 exit(l); } while (1) { fscanf (fin, prim[nump]); if (prim[nump][O] != nump++; else break; } ndata = 0; while (fscanf (fin, data+ndata) == 1) ndata += strlen(data+ndata); start [0] = 1; best = 0; for (Iv = 0; Iv < ndata; lv++) if (start[lv]) { best = Iv; for (Iv2 = 0; Iv2 < nump; Iv

22、2++) { for (Iv3 = 0; Iv + Iv3 < ndata && prim[lv2][lv3] && prim[lv2][lv3] == data[lv+lv3]; Iv3++) ■ / if (!prim[lv2][lv3j) start[lv + Iv3] = 1; } } if (start[ndata]) best = ndata; fprintf (fout, best); return 0; } USACO 3.1 Score Inflation 題目如下： 我們試著設計我們的競賽以便人們能盡可能的多得分，這需要你的幫助。 我們可以從

23、幾個種類中選取競賽的題目，這里的一個“種類”是指一個競賽題目的集合，解 決集合中的題目需要相同多的時間并且能得到相同的分數(shù)。 你的任務是寫一個程序來告訴USACO的職員，應該從每一個種類中選取多少題目，使得 解決題目的總耗時在競賽規(guī)定的時間里并且總分最大。 輸入包括競賽的時間,<= M <= 10,000)和N,“種類"的數(shù)目1 <= N <= 10,000o 后面的每一行將包拾兩個整數(shù)來描述一個”種類”： 第一個整數(shù)說明解決這種題目能得的分數(shù)(1 <= points <= 10000),第二整數(shù)說明解決這種 題目所需的時間(1 <= minutes <= 10000)0 你的程序應

24、該確定我們應該從每個“種類”中選多少道題目使得能在競賽的時間中得到 最大的分數(shù)。 來自任意的”種類“的題目數(shù)目可能任何非負數(shù)(0或更多)。 計算可能得到的最大分數(shù)。 PROGRAM NAME: inflate INPUT FORMAT 第1行:M,N-競賽的時間和題目”種類”的數(shù)目。 第2-N+1行：兩個整數(shù):每個”種類“題目的分數(shù)和耗時。 SAMPLE INPUT (file inflate.in) 300 4 100 60 250 120 120 100 35 20 OUTPUT FORMAT 單獨的一行包括那個在給定的限制里可能得到的最人的分數(shù)。 SAMPL

25、E OUTPUT (file inflate.out) 605 {從第2個“種類”中選兩題，第4個“種類”中選三題} 示例程序如下： #include ifstream fin ("inflate.in11); ofstream fout(,,inflate.outH); const short maxm = 10010; long best[maxm], m, n; void main() { short \, ], lenz pts; fin ? m ? n; for (j = 0; j <= m; j++) best[j] = 0;

26、 for (i = 0; i < n; i++) { fin ? pts ? len; for (j = len; j <= m; j++) if (best[j-len] + pts > best[j]) best[j] = best[j-len] + pts; } fout ? bestfm] ? endl; //由于數(shù)組元素不減，末元素最大 } USACO 3.3 A Game 題目如下： 有如下一個雙人游戲:N(2 <= N <= 100)個正整數(shù)的序列放在一個游戲平臺上，兩人輪流 從序列的兩端取數(shù)，取數(shù)后該數(shù)字被去掉并累加到本玩家的得分中，當數(shù)取盡時，游戲結束。

27、以最終得分多者為勝。 編一個執(zhí)行最優(yōu)策略的程序，最優(yōu)策略就是使自己能得到在當前情況下最人的可能的總 分的策略。你的程序要始終為第二位玩家執(zhí)行最優(yōu)策略。 PROGRAM NAME:gamel INPUT FORMAT 第一行：正整數(shù)N,表示序列中正整數(shù)的個數(shù)。 第二行至末尾：用空格分隔的N個正整數(shù)(大小為1-200)o SAMPLE INPUT (file gamel.in) 6 4729 52 OUTPUT FORMAT 只有一行，用空格分隔的兩個整數(shù)：依次為玩家一和玩家二最終的得分。 SAMPLE OUTPUT (file gamel.out) 18 11 參考程

28、序如下： #include #define NMAX 101 int best[NMAX][2Lt[NMAX]; int n; void readx () { int \f aux; freopen ("gamel.irf： T： stdin); scant &n); for (i = 1; i <= n; i++) { scanf ("%cT： &aux); t = t[i -1] + aux; } fclose (stdin); } inline int min (int x, int y) { return x > y ? y :

29、x; } void solve () { int \, I; for (I = 1; I <= n; I++) for (i = 1; i + I <二 n + 1; i++) best[l%2] = t[i + I -1] - t[i -1] - min (best[i + l][(l -1) % 2], best[(l? 1) % 2]); } void writex () { freopen ("gamel.out", "w", stdout); printf ("%d %d\n,,/ best[l][n % 2], t[n] - best[l][n % 2]);

30、 fclose (stdout); } int main () { readx (); solve (); writex (); return 0; } USACO 3.4 Raucous Rockers 題目如下： 你剛剛得到了流行的“破鑼搖滾”樂隊錄制的尚未發(fā)表的N(1 <= N <= 20)首歌的版權。 你打算從中精選一些歌曲，發(fā)行M(l<=M<=20)張CD。每一張CD最多可以容納T(K=T<= 20)分鐘的音樂，一首歌不能分裝在兩張CD中。 不巧你是一位占典音樂迷，不懂如何判定這些歌的藝術價值。于是你決定根據(jù)以下標準 進行選擇： 歌曲必須按照創(chuàng)作的時間順序

31、在CD盤上出現(xiàn)。 選中的歌曲數(shù)目盡可能地多。 PROGRAM NAME: rockers INPUT FORMAT 第一行：三個整數(shù)：N,T,M. 第二行：N個整數(shù)，分別表示每首歌的長度，按創(chuàng)作時間順序排列。 SAMPLE INPUT (file rockers.in) 452 4342 OUTPUT FORMAT 一個整數(shù),表示可以裝進M張CD盤的樂曲的最人數(shù)目。 SAMPLE OUTPUT (file rockers.out) 3 參考程序如下： #include #define MAX 25 int dp[MAX][MAX][MAX]z

32、 length[MAX]; int main () { FILE *in = fopen ("rockers.in蔦"r")； FILE *out = fopen ("rockers.out", "w"); int a, b, c, d, best, numsongs, cdlength, numeds; fscanf (in, ”％d%d%d： &numsongs, &cdlength, &numeds); for (a = 1; a <= numsongs; a++) fscanf (in, & length [a]); best = 0; for (a = 0; a

33、 < numeds; a++) for (b = 0; b <= cdlength; b++) for (c = 0; c <= numsongs; C++) { for (d = c + 1; d <= numsongs; d++) { if (b + length[d] <= cdlength) { if (dp[a][c] + 1 > dp[a][b + length[d]][d]) dp[a][b + length[d]][d] = dp[a][c] + 1; } else { if (dp[a][c] + 1 > dp[a + l][length[d]][d])

34、dp[a + l][length[d]][d] = dp[a][c] + l; } } if (dp[a][c] > best) best = dp[a][c]; } fprintf (out, "%d\rV； best); return 0; } 解決背包問題 動態(tài)規(guī)劃的定義： 動態(tài)規(guī)劃的基本思想是把待求解的問題分解成若干個子問題，先求解子問題，然后再從這些 子問題的解得到原問題的解，其中用動態(tài)規(guī)劃分解得到的子問題往往不是互相獨立的。動態(tài) 規(guī)劃在查找有很多重疊子問題的情況的最優(yōu)解時有效。它將問題重新組合成子問題。為了避 免多次解決這些子問題，它們的結呆都逐漸被計算并被保

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

36、態(tài)規(guī)劃，回溯法，分支定界法都是解決0-1背包問題的方法。背包問題 與0-1背包問題的不同點在于在選擇物品裝入背包時，可以只選擇物品的一部分，而不一定 是選擇物品的全部。在這里，我們組用的有貪心法和動態(tài)規(guī)劃法來對這個問題進行算法的分 析設計。用動態(tài)規(guī)劃的方法可以看出如果通過第n次選擇得到的是一個最優(yōu)解的話，那么第 n-1次選擇的結果一定也是一個最優(yōu)解。這符合動態(tài)規(guī)劃中最優(yōu)子問題的性質。動態(tài)規(guī)劃方 法是處理分段過程最優(yōu)化一類問題極其有效的方法。在實際生活中，有一類問題的活動過程 可以分成若干個階段，而且在任一階段后的行為依賴于該階段的狀態(tài)，與該階段之前的過程 是如何達到這種狀態(tài)的方式無關。這類問題

37、的解決是多階段的決策過程。考慮用動態(tài)規(guī)劃的 方法來解決，這里的： 階段是：在前n件物品中，選取若干件物品放入背包中； 狀態(tài)是：在前n件物品中，選取若干件物品放入所剩空間為w的背包中的所最人價值； 決策是：第n件物品放或者不放；由此可以寫出動態(tài)轉移方程： 我們用f[i,j]表示在前i件物品中選擇若干件放在所?？臻g為j的背包里所能獲得最犬價值 是:f[i/j]=max{f[i-l/j-wi]+pi(j>=wi)/f[i-l,j]}o這樣，我們可以自底向上地得出在前m件物品中 取出若干件放進背包能獲得的最人價值，也就是f[m,w]令f(i,j)表示用前i個物體裝出重量為 j的組合時的最大價值

38、 f(ij)=max{f(i-l,j)z f(i-l, j-w[i])+v[i]} ,i>0, j>=w[i]; f(i,j) = f(i-lj), i>0z j=w[0]; f(oj) = 0, i=0, j

39、; 〃5個物體各自的價值 intc = 10; //MA 載重 int f[][] = new int⑸[c+1]; //前i個物體裝出重量為j的組合時的最人價值 int maxValue = 0; for(in t j=0; j<=c; j++){ if(j>=w[0]) f[O][j] =V[O]; else f[o]U] = o； } for(int i=l; i=f[i-l]U-w[i]]

40、+v[i]) else System.out.println(f [4] [c]); } } topcoder srm 442 d2 背包問題 n個正整數(shù)，可能有重復，現(xiàn)在要找出兩個不相交的子集A和B, A和B不必覆蓋所有元素, 使A中元素的和SUM(A)與B中元素的和SUM(B)相等，且SUM(A)和SUM(B)盡可能人。 int MX = 500000; int[J c = new int[2,MX*2 + 1]; int T; int function(int[] d) { int i,j; for(i=0;i <= MX * 2;i++) c[TJ] =-1；

41、 c[T,MX] = 0; for(i=0;i