動(dòng)態(tài)規(guī)劃實(shí)驗(yàn)報(bào)告

1、華東師范大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系上機(jī)實(shí)踐報(bào)告一、 內(nèi)容與設(shè)計(jì)思想1對于以下5 個(gè)矩陣：M1: 23, M2: 36, M3: 64, M4: 42, M5: 27 ,(a) 找出這5個(gè)矩陣相乘需要的最小數(shù)量乘法的次數(shù)。(b) 請給出一個(gè)括號化表達(dá)式，使在這種次序下達(dá)到乘法的次數(shù)最少。輸入：第一行為正整數(shù)N,表示有N組測試數(shù)據(jù)；每組測試數(shù)據(jù)的第一行為n,表示有n個(gè)矩陣,2=n=50；接下去的n行,每行有兩個(gè)整數(shù)x和y,表示第ni個(gè)矩陣是x*y的。輸出：對行每組數(shù)據(jù),輸出一行,每行一個(gè)整數(shù),最小的矩陣連乘積。我們保證輸出的結(jié)果在264之內(nèi)?；舅枷耄簩τ趎個(gè)矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。

2、由于每種加括號方式都可以分解為兩個(gè)子矩陣的加括號問題：(A1.Ak)(Ak+1An)可以得到關(guān)于P(n)的遞推式如下：2定義0/1/2背包問題為：。限制條件為：，且。設(shè)f(i , y)表示剩余容量為y，剩余物品為：i，i+1，n時(shí)的最優(yōu)解的值。1）給出f(i , y)的遞推表達(dá)式；2）請?jiān)O(shè)計(jì)求解f(i , y)的算法，并實(shí)現(xiàn)你的算法；3）設(shè)W=10,20,15,30，P=6,10,15,18,c=48，請用你的算法求解。輸入：第一行為一個(gè)正整數(shù)N，表示有幾組測試數(shù)據(jù)。每組測試數(shù)據(jù)的第一行為兩個(gè)整數(shù)n和M，0n=20,0M。再下去的n行每行有兩個(gè)整數(shù)Wi和Pi, 0Wi,Pi10000。輸出：對

3、行每組數(shù)據(jù),輸出一行,每行一個(gè)整數(shù),最小的矩陣連乘積。我們保證輸出的結(jié)果在264之內(nèi)?；舅枷耄簩Φ?i 個(gè)物品代價(jià)w ，價(jià)值v，for(i=1;i=wi;j-)if(dpjdpj-wi+vi)dpj=dpj-wi+vi;3設(shè)G為有n個(gè)頂點(diǎn)的有向無環(huán)圖，G中各頂點(diǎn)的編號為1到n，且當(dāng)為G中的一條邊時(shí)有i j。設(shè)w(i，j)為邊的長度，請?jiān)O(shè)計(jì)動(dòng)態(tài)規(guī)劃算法，計(jì)算圖G中最長路徑。并分析算法的時(shí)間復(fù)雜性。輸入：輸入一個(gè)數(shù)n(1=n=200)，表示有n個(gè)點(diǎn)，接下來一個(gè)數(shù)m，表示有m條路，接下來m行中每行輸入2個(gè)數(shù)a ，b，v表示從a點(diǎn)到b點(diǎn)有條路，路的長度為v。接下來輸入一個(gè)數(shù)p，表示有p次詢問，在接下

4、來的p行中每行輸入2個(gè)數(shù)a,b，算出此圖中從a到b的最長路徑。輸出：對每個(gè)詢問p，(a,b)，輸出從a到b之間的最長路.如果a,b之間沒連通，輸出1?；舅枷耄篎loyd算法。時(shí)間復(fù)雜度是O(n3).4 【裝箱問題】：有一個(gè)箱子容量為V（正整數(shù)，0V20000），同時(shí)有 個(gè)物品（030），每個(gè)物品有一個(gè)體積（正整數(shù)）。要求從個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。輸入：輸入有多組測試數(shù)據(jù)，第一行一個(gè)正整數(shù)V,表示箱子的容量第二行一個(gè)數(shù)據(jù)n表示物品個(gè)數(shù)。第三行有n個(gè)數(shù)據(jù)，描述每個(gè)物品的體積輸出：每個(gè)輸出占一行，輸出箱子最后剩下的最小體積基本思想：類似0-1背包問題，弄成0-1背包的

5、反面，看0-1背包那些值可以達(dá)到，再用n減去離他最近的比他小的值即為所得。5【數(shù)字三角形】：給定一個(gè)具有層的數(shù)學(xué)三角形，從頂至底有多條路徑，每一步可沿左斜線向下或沿右斜線向下，路徑所經(jīng)過的數(shù)字之和為路徑得分，請求出最小路徑得分及相應(yīng)路徑。輸入：輸入數(shù)據(jù)首先包括一個(gè)整數(shù)C,表示測試實(shí)例的個(gè)數(shù)，每個(gè)測試實(shí)例的第一行是一個(gè)整數(shù)N(1 = N = 100)，表示數(shù)塔的高度，接下來用N行數(shù)字表示數(shù)塔，其中第i行有個(gè)i個(gè)整數(shù)，且所有的整數(shù)均在區(qū)間0,99內(nèi)。輸出：對于每個(gè)測試實(shí)例，輸出可能得到的最小和。并在下一行輸出路徑?；舅枷耄簭纳贤卤闅v，每一層每一個(gè)數(shù)都記錄從1到它的最小值，最后從最后一層中找出最

6、小數(shù)即可。二、 調(diào)試過程三、 附錄1）完全加括號的矩陣連乘積#includeint p51;_int64 m5151;int f(int n)int i,j,k;for(i=1;i=n;i+)mii=0;for(k=1;kn;k+)for(i=1;i=n-k;i+)mii+k=mii+mi+1i+k+pi-1*pi*pi+k;for(j=i+1;jmij+mj+1i+k+pi-1*pj*pi+k)mii+k=mij+mj+1i+k+pi-1*pj*pi+k;return 0;int main()int N,n,i;scanf(%d,&N);while(N-)scanf(%d,&n);for(i

7、=0;in;i+)scanf(%d%d,&pi,&pi+1);f(n);printf(%I64dn,m1n);2）0-1背包問題#includeint w25,v25;int dp;int main()int n,m,N;int i,j;scanf(%d,&N);while(N-)scanf(%d%d,&n,&m);for(i=1;i=n;i+)scanf(%d%d,&wi,&vi);for(i=1;i=m;i+)dpi=0;for(i=1;i=wi;j-)if(dpjdpj-wi+vi)dpj=dpj-wi+vi;printf(%dn,dpm); 3）最長路#includeint x2012

8、01;int main()int i,j,k;int n,m;int a,b,v,p;while(scanf(%d%d,&n,&m)!=EOF)for(i=1;i=n;i+)for(j=1;j=n;j+)xij=0;for(i=1;i=m;i+)scanf(%d%d%d,&a,&b,&v);xab=v;for(i=1;i=n;i+)for(j=i+1;j=n;j+)for(k=i+1;kxij)xij=xik+xkj;scanf(%d,&p);while(p-)scanf(%d%d,&a,&b);if(xab=0)printf(-1n);else printf(%dn,xab);4）裝箱問題#

9、includeint w31;int dp20001;int main()int n,N;int i,j;while(scanf(%d,&N)!=EOF)scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&wi);for(i=0;i=N;i+)dpi=0;dp0=1;for(i=1;i=0;j-)if(dpj=1&(j+wi)=N)dpj+wi=1;for(i=N;dpi=0;i-);printf(%dn,N-i);5）數(shù)塔#includeint a101101;int min101101;int main()int N,n,i,j,x;scanf(%d,&N);while(N-)scanf(%d,&n);for(i=1;i=n;i+)for(j=1;j=i;j+)scanf(%d,&ai