動(dòng)態(tài)規(guī)劃應(yīng)用

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

2、取，對(duì)應(yīng)于一個(gè)策略可以確定活動(dòng)的效果，這個(gè)效果可以用數(shù)量來確定。策略 不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個(gè)最優(yōu)策略，使在 預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果.動(dòng)態(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)

3、C,而第四個(gè)階段是點(diǎn)C到點(diǎn)D。狀態(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)D。過程的狀態(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ù)的處理將會(huì)有很大的好

4、處。此外，狀態(tài)可以有多個(gè)分量（多維情形）， 因而用向量來代表；而且在每個(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è)性

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

6、策略。給定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)確定的對(duì)應(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)策略，它滿足：相對(duì)前面決策所形成的狀態(tài)而言，余下的子策略 必然構(gòu)成最優(yōu)子策略”。D也是B1到D的最短路徑.事實(shí)正是如此，因此我們認(rèn)為這個(gè)例子滿足最優(yōu)性原理的要求。 0C20C2是A到C2的最短路徑，B

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

8、,有四種方法能劃分集合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ù)，如果不存在這樣的劃分方案，則輸出0。程序不能預(yù) 存結(jié)果直接輸出。PROGRAM NAME: subsetINPUT FORMAT輸入文件只有一行，且只有一個(gè)整數(shù)NSAMPLE INPUT (file subset.in)7OUTPUT FORMAT輸出劃分方案總數(shù)，如果不存在則輸出0。

9、SAMPLE OUTPUT (file subset.out)4參考程序如下：#include 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 main() fin n;fin.close();int s = n*(n+1);if (s % 4) fout 0 endl;fout.close ();return ;s /= 4;int i, j;

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

11、：A, AB, BA, CA, BBC序列S的前面K個(gè)字符稱作S中長(zhǎng)度為K的前綴。設(shè)計(jì)一個(gè)程序，輸入一個(gè)元素集合以及一 個(gè)大寫字母序列，計(jì)算這個(gè)序列最長(zhǎng)的前綴的長(zhǎng)度。PROGRAM NAME: prefixINPUT FORMAT輸入數(shù)據(jù)的開頭包括1.200個(gè)元素(長(zhǎng)度為1.10)組成的集合，用連續(xù)的以空格分開的字 符串表示。字母全部是大寫，數(shù)據(jù)可能不止一行。元素集合結(jié)束的標(biāo)志是一個(gè)只包含一個(gè).的行。 集合中的元素沒有重復(fù)。接著是大寫字母序列S，長(zhǎng)度為1.200,000，用一行或者多行的字符串 來表示，每行不超過76個(gè)字符。換行符并不是序列S的一部分。SAMPLE INPUT (file pr

12、efix.in)A AB BA CA BBCABABACABAABCOUTPUT FORMAT只有一行，輸出一個(gè)整數(shù)，表示S能夠分解成P中元素的最長(zhǎng)前綴的長(zhǎng)度。SAMPLE OUTPUT (file prefix.out) 11示例程序如下：#include #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, lv

13、2, lv3;if (fin = fopen(prim.in, r) = NULL)perror (fopen fin);exit(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 = 1

14、;best = 0;for (Iv = 0; Iv 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);return 0;USACO 3.1 Score Inflation題目如下：我們?cè)囍O(shè)計(jì)

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

16、s = 10000)。你的程序應(yīng)該確定我們應(yīng)該從每個(gè)”種類”中選多少道題目使得能在競(jìng)賽的時(shí)間中得到最大的分?jǐn)?shù)。來自任意的”種類”的題目數(shù)目可能任何非負(fù)數(shù)(0或更多)。計(jì)算可能得到的最大分?jǐn)?shù)。PROGRAM NAME: inflateINPUT FORMAT第1行：M, N-競(jìng)賽的時(shí)間和題目”種類”的數(shù)目。第2-N + 1行：兩個(gè)整數(shù):每個(gè)”種類”題目的分?jǐn)?shù)和耗時(shí)。SAMPLE INPUT (file inflate.in)300 4100 60250 120120 10035 20OUTPUT FORMAT單獨(dú)的一行包括那個(gè)在給定的限制里可能得到的最大的分?jǐn)?shù)。SAMPLE OUTPUT (fi

17、le inflate.out)605從第2個(gè)”種類”中選兩題，第4個(gè)種類”中選三題示例程序如下：#include ifstream fin(inflate.in);ofstream fout(inflate.out);const short maxm = 10010;long bestmaxm, m, n;voidmain()short i, j, len, pts;fin m n;for (j = 0; j = m; j+)bestj = 0;for (i = 0; i pts len;for (j = len; j bestj)bestj = bestj-len + pts;fout be

18、stm endl; /由于數(shù)組元素不減，末元素最大USACO 3.3 A Game題目如下：有如下一個(gè)雙人游戲:N(2 = N = 100)個(gè)正整數(shù)的序列放在一個(gè)游戲平臺(tái)上，兩人輪流從序 列的兩端取數(shù)，取數(shù)后該數(shù)字被去掉并累加到本玩家的得分中，當(dāng)數(shù)取盡時(shí)，游戲結(jié)束。以最終得分 多者為勝。編一個(gè)執(zhí)行最優(yōu)策略的程序，最優(yōu)策略就是使自己能得到在當(dāng)前情況下最大的可能的總分的策略。 你的程序要始終為第二位玩家執(zhí)行最優(yōu)策略。PROGRAM NAME: game1INPUT FORMAT第一行：正整數(shù)N,表示序列中正整數(shù)的個(gè)數(shù)。第二行至末尾：用空格分隔的N個(gè)正整數(shù)(大小為1-200)。SAMPLE INPU

19、T (file game1.in)64 7 2 95 2OUTPUT FORMAT只有一行，用空格分隔的兩個(gè)整數(shù)：依次為玩家一和玩家二最終的得分。SAMPLE OUTPUT (file gamel.out)18 11參考程序如下：#include #define NMAX 101int bestNMAX2, tNMAX;int n;voidreadx () int i, aux;freopen (game1.in”, r, stdin);scanf (%d”, &n);for (i = 1; i y ? y : x;voidsolve () int i, l;for (l = 1; l = n

20、; l+)for (i = 1; i + l = n + 1; i+)bestl%2 = ti + l - 1 - ti - 1 - min (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);intmain () readx ();solve ();writex ();return 0;USACO 3.4 Raucous Rockers題目如下：你剛剛得

21、到了流行的破鑼搖滾”樂隊(duì)錄制的尚未發(fā)表的N(1 = N = 20)首歌的版權(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ù)目盡可能地多。PROGRAM NAME: rockers INPUT FORMAT 第一行：三個(gè)整數(shù)：N, T, M.第二行：N個(gè)整數(shù)，分別表示每首歌的長(zhǎng)度，按創(chuàng)作時(shí)間順序排列。SAMPLE INPUT (file rocke

22、rs.in) 4 5 2 4 3 4 2OUTPUT FORMAT一個(gè)整數(shù)，表示可以裝進(jìn)M張CD盤的樂曲的最大數(shù)目。SAMPLE OUTPUT (file rockers.out) 3參考程序如下：#include #define MAX 25 int dpMAXMAXMAX, lengthMAX; int main () FILE *in = fopen (rockers.in, r);FILE *out = fopen (rockers.out, w);int a, b, c, d, best, numsongs, cdlength, numcds;fscanf (in, %d%d%d,

23、&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 = numsongs; c+) for (d = c + 1; d = numsongs; d+) if (b + lengthd dpab + lengthdd) dpab + lengthdd = dpac + 1;else if (dpac + 1 dpa +

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

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

26、品的一部分，而不一定是選擇物品的全部。在這里， 我們組用的有貪心法和動(dòng)態(tài)規(guī)劃法來對(duì)這個(gè)問題進(jìn)行算法的分析設(shè)計(jì)。用動(dòng)態(tài)規(guī)劃的方法可以看出如 果通過第n次選擇得到的是一個(gè)最優(yōu)解的話，那么第n-1次選擇的結(jié)果一定也是一個(gè)最優(yōu)解。這符合 動(dòng)態(tài)規(guī)劃中最優(yōu)子問題的性質(zhì)。動(dòng)態(tài)規(guī)劃方法是處理分段過程最優(yōu)化一類問題極其有效的方法。在實(shí) 際生活中，有一類問題的活動(dòng)過程可以分成若干個(gè)階段，而且在任一階段后的行為依賴于該階段的狀 態(tài)，與該階段之前的過程是如何達(dá)到這種狀態(tài)的方式無關(guān)。這類問題的解決是多階段的決策過程?？?慮用動(dòng)態(tài)規(guī)劃的方法來解決，這里的：階段是：在前n件物品中，選取若干件物品放入背包中；狀態(tài)是：在前n件

27、物品中，選取若干件物品放入所剩空間為w的背包中的所最大價(jià)值；決策是：第n件物品放或者不放；由此可以寫出動(dòng)態(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 ,i0, j=wi;f(i,j) = f(i-1,j) , i0, j=w0;f(0,j) = 0, i=0, jw0;代碼實(shí)現(xiàn)：package zyf;public class bagPro public static void main(String args) / TODO自動(dòng)生成方法存根int w = 2,2,6,5,4; /5個(gè)物體各自的重量int v = 6,3,5,4,6; /5個(gè)物體各自的價(jià)值int c = 10; /最