動(dòng)態(tài)規(guī)劃-0-1背包ppt課件

1、數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)適用專業(yè)： 軟件工程（本科） 學(xué)時(shí)： 32 平頂山學(xué)院軟件學(xué)院呂海蓮 E-Mail：lvhailian_實(shí)訓(xùn)3：動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃-0-1背包問題背包問題問題描述：給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?對(duì)于一種物品，要么裝入背包，要么不裝。所以對(duì)于一種物品的裝入狀態(tài)可以取0和1.我們?cè)O(shè)物品i的裝入狀態(tài)為xi,xi(0,1)，此問題稱為0-11背包問題0-1背包問題背包問題0-1背包問題是一個(gè)特殊的整數(shù)規(guī)劃問題?？擅枋鋈缦拢簄ixCxwxviniiiniii1,1 , 0max11過程分析過程

2、分析 背包的最大容量為10，那么在設(shè)置數(shù)組m大小時(shí)，可以設(shè)行列值為5和10，那么，對(duì)于m(i,j)就表示可選物品為in背包容量為j(總重量)時(shí)背包中所放物品的最大價(jià)值。 0 1 2 3 4 5 6 7 8 9 10 j1 2 3 4 5 數(shù)據(jù)：物品個(gè)數(shù)n=5,物品重量wn=2，2，6，5，4,物品價(jià)值Vn=6，3，5，4，6,總重量c=10.最優(yōu)值過程分析最優(yōu)值過程分析 背包中的物品設(shè)為空，首先，我們先對(duì)物品n放入背包的情況做分析,即在總重量分別為0到10時(shí),如何放置物品n,使總價(jià)值最大，此時(shí)要確定m(5,0.10)11個(gè)元素的值。 如果物品n的重量超過背包允許的總重量,則物品n不放入背包,此

3、時(shí)背包中物品的總價(jià)值為0，否則，如果物品n裝入背包后不超重，則裝入物品n，此時(shí)背包的總價(jià)值為物品n的價(jià)值vn。00006666666 0 1 2 3 4 5 6 7 8 9 10 j1 2 3 4 5 2 2 6 5 4 w 6 3 5 4 6 v 因w5=4,所以，當(dāng)背包容量j小于w5時(shí)，物品5時(shí)不能放入的，所以當(dāng)前的背包總價(jià)值都為0。當(dāng)j=w5時(shí)，物品5可以放入背包，此時(shí)當(dāng)前的背包總價(jià)值都為v5.最優(yōu)值過程分析最優(yōu)值過程分析 然后，我們?cè)趯?duì)物品5處理后的基礎(chǔ)上，對(duì)物品4進(jìn)行分析。此時(shí)我們的任務(wù)是要確定m(4,0.10)11個(gè)元素的值。用同樣的方法，對(duì)物品4的處理有兩種情況：w4大于j和w4

4、小于j。 1.w4j，當(dāng)背包容量j小于w4時(shí)，物品4時(shí)不能放入的，所以當(dāng)前的背包總價(jià)值與4+1.n保持一致，即m(4,j)=m(5,j)。 即0000600006666666 0 1 2 3 4 5 6 7 8 9 10 j1 2 3 4 5 2 2 6 5 4 w 6 3 5 4 6 v m(4,0-4)=m(5,0-4) 最優(yōu)值過程分析最優(yōu)值過程分析 2.當(dāng)j=w4時(shí)，對(duì)物品4要么放入要么不放入，最優(yōu)值的選擇標(biāo)準(zhǔn)應(yīng)依據(jù)總價(jià)值，總價(jià)值高的作為最優(yōu)值。如：m(4,5),w4不放入時(shí),原值，總價(jià)值是6=m(4+1,5),00006600006666666 0 1 2 3 4 5 6 7 8 9

5、10 j1 2 3 4 5 2 2 6 5 4 w 6 3 5 4 6 v 當(dāng)w4放入時(shí)，則要配合其前邊的最優(yōu)值，即w4的放入，使剩余物品(4+1.n)的最大容量變?yōu)閖-w4,此時(shí)背包中的最大容量為m(4+1,j-w4)的值0加上v4的值4，然后比較w4放入與否的總價(jià)值，因此m(4,5)選擇w4不放入背包，最優(yōu)值是依然是6。最優(yōu)值過程分析最優(yōu)值過程分析以此類推，完成m(4,6.10)的最優(yōu)值000066600006666666 0 1 2 3 4 5 6 7 8 9 10 j1 2 3 4 5 2 2 6 5 4 w 6 3 5 4 6 v 那么，m(4,7), m(4,8),m(4,9),m

6、(4,10)的值分別為： m( 5 , 6)=6 m( 5 , 6-5 )+ 4=4 m(4 , 6)=max(6,4)=6 i j i+1 j i+1 j-wi vi 6 6 10 10最優(yōu)值過程分析最優(yōu)值過程分析填充m(3,1.10)的最優(yōu)值000066666101000006666666 0 1 2 3 4 5 6 7 8 9 10 j1 2 3 4 5 2 2 6 5 4 w 6 3 5 4 6 v 那么，m(3,0.10的值分別為： m( i+1 , j ) m( i+1 , j-wi )+ vi 0:0 1:0 2:03:0max4:6 5:66: 67:68:69:1010:11

7、最優(yōu)值過程分析最優(yōu)值過程分析填充m(2,0.10)的最優(yōu)值0000666661011000066666101000006666666 0 1 2 3 4 5 6 7 8 9 10 j1 2 3 4 5 2 2 6 5 4 w 6 3 5 4 6 v 那么，m(2,0.10）的值分別為： m( i+1 , j ) m( i+1 , j-wi )+ vi 0:0 1:0 2:33:3max4:6 5:66: 97:98:99:1010:11最優(yōu)值過程分析最優(yōu)值過程分析計(jì)算原問題的最優(yōu)值00336699910110000666661011000066666101000006666666 0 1 2

8、3 4 5 6 7 8 9 10 j1 2 3 4 5 2 2 6 5 4 w 6 3 5 4 6 v c=10w1,所以，m(1,10)=max(m(2,10),m(2,c-w1)+v1) 同樣，如果w1大于c，則w1不放入，m( 1 ,c )=m(2,c)，否則，從放與不放的最大值中選擇最優(yōu)值。 =max(11,m(2,8)+6)=max(11,15)=15 依此計(jì)算m(1,0.9)的值最優(yōu)值過程分析最優(yōu)值過程分析m的最終結(jié)果如下表006699121215151500336699910110000666661011000066666101000006666666 0 1 2 3 4 5 6

9、 7 8 9 10 j1 2 3 4 5 2 2 6 5 4 w 6 3 5 4 6 v 遞歸定義最優(yōu)值遞歸定義最優(yōu)值 由前面的最優(yōu)值過程分析實(shí)例，根據(jù)0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式：nnniiiiwjwjvjnmwjwjjimvwjimjimjim00),(0), 1(), 1(), 1(max),(構(gòu)造最優(yōu)解構(gòu)造最優(yōu)解 我們可根據(jù)c列的數(shù)據(jù)來構(gòu)造最優(yōu)解，從i=1,j=c即m(i,j)開始，如果m(i,j)=m(i+1,j),則物品wi沒有裝入背包，從而xi=0，否則，物品wi裝入背包，相應(yīng)的xi=1，此時(shí)，為了確定其后繼即k=i+1的xk的值，我們應(yīng)在k行

10、尋找新的j值作為參照。006699121215151500336699910110000666661011000066666101000006666666 0 1 2 3 4 5 6 7 8 9 10 j1 2 3 4 5 2 2 6 5 4 w 6 3 5 4 6 v 如果xi=0，則j=j,否則，j= j-wi ,此時(shí)i=i+1 然后我們重復(fù)上述兩步，計(jì)算新一組(i,j)對(duì)應(yīng)的xi值。直到i=n-1為止。 對(duì)物品n，直接由m(n,j)是否為0確定xn的值是0或1。構(gòu)造最優(yōu)解構(gòu)造最優(yōu)解 結(jié)果示例：006699121215151500336699910110000666661011000066

11、666101000006666666 0 1 2 3 4 5 6 7 8 9 10 j1 2 3 4 5 2 2 6 5 4 w 6 3 5 4 6 v m( i , j) 1, 10,15 m(i+1, j) 2, 10,11x1=1m( i , j) 2, 8, 9 m(i+1 , j) 3, 8, 6j=j-wi=10-2=8 j= j-w2=6x2=1m( i , j) 3, 6, 6 m(i+1 , j) 4, 6, 6j=j=6x3=0m( i , j) 4, 6, 6 m(i+1 , j) 5, 6, 6j=j=6x4=0 m( i , j)0 5, 6,6x5=1所以，原問題的

12、最優(yōu)解是(1,1,0,0,1),c=8,總價(jià)值=15動(dòng)態(tài)規(guī)劃思想動(dòng)態(tài)規(guī)劃思想動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題。但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級(jí)。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，為此，可以用一個(gè)表來記錄所有已解決的子問題的答案而不管該答案是否用到，這就是動(dòng)態(tài)規(guī)劃的基本思想。動(dòng)態(tài)規(guī)劃基本步驟動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息

13、，構(gòu)造最優(yōu)解。1-最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)子結(jié)構(gòu)性質(zhì)：動(dòng)態(tài)規(guī)劃算法的第一步是要刻畫最優(yōu)解的結(jié)構(gòu)，即當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征 對(duì)于0-1背包問題，其最優(yōu)子結(jié)構(gòu)性質(zhì)如下： 設(shè)(y1,y2,yn)是0-1背包問題的一個(gè)最優(yōu)解，則(y2,y3,yn)則是下面相應(yīng)子問題的一個(gè)最優(yōu)解: maxi=2 nviyii=2 nwiyi c-w1y1yi0,1,2 i n2-遞歸定義最優(yōu)值遞歸定義最優(yōu)值 由前面的最優(yōu)值過程分析實(shí)例，根據(jù)0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i，j)的遞歸式：n

14、nniiiiwjwjvjnmwjwjjimvwjimjimjim00),(0), 1(), 1(), 1(max),(動(dòng)態(tài)規(guī)劃算法分析：p723-計(jì)算最優(yōu)值計(jì)算最優(yōu)值 根據(jù)前邊的分析過程設(shè)計(jì)相應(yīng)的算法，我們可從wn開始以自底向上的方式計(jì)算出最優(yōu)值；完成m(1.n,0.c)的數(shù)據(jù)填充 jmax=min(wn-1,c);/當(dāng)前n物品不能裝入的背包容量 for(j=0;j=jmax;j+)mnj=0;/背包容量小于wn時(shí)不裝入for(j=wn;j1;i-) jmax=min(wi-1,c);wi不能裝入的臨界值 for(j=0;j=jmax;j+)mij=mi+1j ;/vi不能裝入的容量 for(

15、j=wi;j=w1) w1c=max(m1c,m2c-w1+v1);4-構(gòu)造最優(yōu)解構(gòu)造最優(yōu)解 我們可根據(jù)c列的數(shù)據(jù)來構(gòu)造最優(yōu)解，從i=1,j=c即m(i,j)開始，如果m(i,j)=m(i+1,j),則物品wi沒有裝入背包，從而xi=0，否則，物品wi裝入背包，相應(yīng)的xi=1，此時(shí)，為了確定其后繼即k=i+1的xk的值，我們應(yīng)在k行尋找新的j值作為參照。對(duì)物品n，直接由m(n,j)是否為0確定xn的值是0或1 for(i=1;i0) xn=1;else xn=0; 背包中裝入的重量和價(jià)值可以通過最優(yōu)質(zhì)求得。實(shí)訓(xùn)實(shí)訓(xùn)2：設(shè)計(jì)要求：設(shè)計(jì)要求 窗體設(shè)計(jì)基本要求：用戶輸入信息：物品個(gè)數(shù)、物品重量及價(jià)值

16、、背包容量；輸出信息：裝入背包的物品序號(hào)、背包的總重量以及所裝入物品的總價(jià)值。在此基礎(chǔ)上擴(kuò)展功能需求。矩陣連乘矩陣連乘問題：設(shè)有給定n個(gè)矩陣A1,A2,.,An，其中Ai與Ai+1是可乘的，i=1,2,.,n-1?？疾爝@n個(gè)矩陣的連乘積A1A2.An。假設(shè)給定兩個(gè)矩陣A1,A2, 它們的維數(shù)分別是m*n,n*p,則計(jì)算A1A2的標(biāo)準(zhǔn)算法怎樣設(shè)計(jì)？關(guān)標(biāo)準(zhǔn)算法中，主要計(jì)算量在三重循環(huán)，問總共需要多少次數(shù)乘？時(shí)間復(fù)雜度是多少？P50,m*n*p，O(n3)矩陣連乘矩陣連乘多矩陣連乘滿足結(jié)合律，假設(shè)給定三個(gè)矩陣A1,A2, A3的維數(shù)分別是10*100，100*5，5*50， 問： A1,A2, A3

17、有多少種組合方式，不同組合方式下各進(jìn)行多少次數(shù)乘運(yùn)算？兩種， (A1A2 ) A3 ) 和(A1 ( A2 A3 ) )， (A1A2 ) A3 )乘運(yùn)算的次數(shù)為(10*100*5)+10*5*50=5000+2500=7500， (A1 ( A2 A3 ) )乘運(yùn)算的次數(shù)為(100*5*50)+10*100*50=25000+50000=75000 不同組合方式下的乘運(yùn)算次數(shù)是不相同的。矩陣連乘矩陣連乘矩陣連乘問題即是對(duì)于給定n個(gè)矩陣A1,A2,An，其中Ai與Ai+1是可乘的，i=1，2，n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。如何確定一個(gè)矩

18、陣連乘積的最優(yōu)的計(jì)算次序，是我們要解決的根本問題，通過傳統(tǒng)的什么方法可以找出最優(yōu)解？窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。 矩陣連乘矩陣連乘設(shè)有四個(gè)矩陣A,B,C,D，它們的維數(shù)分別是：A=5010，B=1040，C=4030，D=305 則總共有五種完全加括號(hào)的方式：(A(BC)D) (A(B(CD) (AB)(CD) (AB)C)D) (A(BC)D)，其數(shù)乘次數(shù)分別為：16000, 10500, 36000, 87500, 34500所以，窮舉搜索法不是一個(gè)有效的算法。下面介紹用動(dòng)態(tài)規(guī)劃法來解決最優(yōu)計(jì)算次序問題。動(dòng)

19、態(tài)規(guī)劃基本步驟動(dòng)態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。3.1 矩陣連乘問題矩陣連乘問題給定n個(gè)矩陣A1,A2,.,An，其中Ai與Ai+1是可乘的，i=1,2,.,n-1?？疾爝@n個(gè)矩陣的連乘積A1A2.An。由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式來確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號(hào)，則可以依此次序反復(fù)調(diào)用2個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃法1.分析最優(yōu)解的結(jié)構(gòu)分析最優(yōu)解的結(jié)構(gòu)

20、預(yù)處理： 將矩陣連乘積AiAi+1.Aj簡記為Ai:j，這里ij。 考察計(jì)算Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，ikj，則其相應(yīng)完全加括號(hào)方式為（AiAi+1. Ak）（Ak+1 Ak+2. Aj ）。 計(jì)算量：Ai:k的計(jì)算量加上Ak+1:j的計(jì)算量，再加上Ai:k和Ak+1:j相乘的計(jì)算量。分析最優(yōu)解的結(jié)構(gòu)：計(jì)算Ai:j的最優(yōu)次序所包含的計(jì)算矩陣子鏈 Ai:k和Ak+1:j的次序也是最優(yōu)的。 矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法求解的顯著特征。2.建立遞歸關(guān)系建立遞歸關(guān)系設(shè)計(jì)算

21、Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mi,j，則原問題的最優(yōu)值為m1,n。當(dāng)i=j時(shí)，Ai:j=Ai，因此，mi,i=0，i=1,2,n。當(dāng)ij時(shí)，mi,j=mi,k+mk+1,j+pi-1pkpj，這里Ai的維數(shù)為pi-1pi?？梢赃f歸地定義mi,j為： k的位置只有j-i種可能。可以看出，在計(jì)算最優(yōu)解mi,j時(shí)要從所有的斷開處遴選，同時(shí)要依據(jù)較小規(guī)模時(shí)的最優(yōu)解。jipppjkmkimjijimjkijki1, 1,min0,3.計(jì)算最優(yōu)值計(jì)算最優(yōu)值由此可見，在遞歸計(jì)算時(shí)，。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。用動(dòng)態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在

22、計(jì)算過程中，保存已解決的子問題答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只要簡單查一下，從而避免大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法。實(shí)例分析實(shí)例分析過程分析：確定如下六個(gè)矩陣連乘的最優(yōu)計(jì)算次序。p521.所有子問題最優(yōu)解的數(shù)據(jù)存貯：由于不同子問題Ai:j(1ijn)的個(gè)數(shù)最多只有O(n2)，在計(jì)算過程中，為了保存已解決的子問題答案（最優(yōu)解和斷點(diǎn)）。我們可以設(shè)置兩個(gè)二維表格m和s1.n1.n來存貯子問題的最優(yōu)解。如下所示：A1A2A3A4A5A63035351515551010202025 則：mij就表示子問題Ai:j即Ai Ai+1 Aj連乘的最優(yōu)解sij就表示其子問題的斷開位置,分解

23、為兩個(gè)最優(yōu)子問題 1 2 3 4 5 61 2 3 4 5 6 i j 實(shí)例分析實(shí)例分析1.最小規(guī)模時(shí)的最優(yōu)解，子問題間距(步長)step為1，即單矩陣，乘運(yùn)算次數(shù)為0，矩陣加括號(hào)及最優(yōu)解設(shè)置結(jié)果如下。 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 61 2 3 4 5 6 i j A1 A2 A3 A4 A5 A6(A1) ( A2 ) ( A3 ) ( A4 ) ( A5 ) ( A6 ) 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 61 2 3 4 5 6 i j 實(shí)例分析實(shí)例分析2.計(jì)算子問題間距(步長)step為2的最優(yōu)解。用到小于2時(shí)的

24、子問題的最優(yōu)解A1 A2 A3 A4 A5 A6當(dāng)計(jì)算mij時(shí)，需要根據(jù)前邊分析的遞歸關(guān)系來進(jìn)行，把所有可能的斷點(diǎn)都進(jìn)行比較，選取最優(yōu)的斷點(diǎn)，并更新s的相應(yīng)值jipppjkmkimjijimjkijki1, 1,min0,當(dāng)step=2時(shí)，表示相鄰矩陣之間加括號(hào)，所以要進(jìn)行處理的中間斷點(diǎn)k的變化次數(shù)都是1(遞歸公式中的i=kj)，我們先分析一般情形的加工算法實(shí)例分析實(shí)例分析3.遞歸公式中mi,j加工算法分析,當(dāng)ij時(shí)mij為Ai+1 Aj最優(yōu)次數(shù)，sij為相應(yīng)斷點(diǎn)jipppjkmkimjijimjkijki1, 1,min0,mij = mii+ mi+1j+ pi-1*pi*pj; /初始化

25、為Aisij = i; /設(shè)Ai為斷點(diǎn)for (int k = i+1; k j; k+) /分別把Ai+1 Aj-1設(shè)為斷點(diǎn) /這里Ai的維數(shù)為pi-1piint t = mik + mk+1j + pi-1*pk*pj;/Ak為斷點(diǎn)if (t mij) mij = t; sij = k; 實(shí)例分析實(shí)例分析4.step=2時(shí)的數(shù)據(jù)加工過程mij = mii+mi+1j+ pi-1*pi*pj; sij = i; /設(shè)Ai為斷點(diǎn)for (int k = i+1; k j; k+) /這里Ai的維數(shù)為pi-1piint t = mik + mk+1j + pi-1*pk*pj;if (t =j,

26、結(jié)束循環(huán)，m1,1=15750 計(jì)算其他四個(gè)子問題的過程:與計(jì)算A1,2 相似，直接賦初始化的值35*15*5， 15*5*10， 5*10*20， 10*20*25，實(shí)例分析實(shí)例分析4.所有step為2的子問題處理完畢后，數(shù)據(jù)結(jié)果如下： 0 0 15750 0 0 2625 0 0 750 0 0 1000 0 0 5000 0 0 1 2 3 4 5 61 2 3 4 5 6 i j 0 0 1 1 0 0 2 2 0 0 3 3 0 0 4 4 0 0 5 5 0 0 1 2 3 4 5 61 2 3 4 5 6 i j 實(shí)例分析實(shí)例分析5.step=3時(shí)的數(shù)據(jù)加工過程mij = mii

27、+mi+1j+ pi-1*pi*pj; sij = i; /設(shè)Ai為斷點(diǎn)for (int k = i+1; k j; k+) /這里Ai的維數(shù)為pi-1piint t = mik + mk+1j + pi-1*pk*pj;if (t mij) mij = t; sij = k; 計(jì)算A1,3的過程:矩陣維數(shù)數(shù)組矩陣維數(shù)數(shù)組p0.6:0 1 2 3 4 5 630 35 15 5 10 20 25A1 A2 A3 A4 A5 A6m 1,2 2,3 3,4 4,5 5,6 15750 2625 750 1000 5000S 1,2 2,3 3,4 4,5 5,6 1 2 3 4 5i j mi,

28、j si,j t 1 3 7875 1 初始化初始化:A1( A2 A3)K=2:( A1 A2 ) A3 7875 1 18000 計(jì)算A2,4的過程:i j mi,j si,j t 2 4 6000 2 初始化初始化:A2( A3 A4)K=3:( A2 A3 ) A4 4375 3 4375 實(shí)例分析實(shí)例分析5.step=3時(shí)的數(shù)據(jù)加工過程mij = mii+mi+1j+ pi-1*pi*pj; sij = i; /設(shè)Ai為斷點(diǎn)for (int k = i+1; k j; k+) /這里Ai的維數(shù)為pi-1piint t = mik + mk+1j + pi-1*pk*pj;if (t

29、mij) mij = t; sij = k; 計(jì)算A3,5的過程:矩陣維數(shù)數(shù)組矩陣維數(shù)數(shù)組p0.6:0 1 2 3 4 5 630 35 15 5 10 20 25A1 A2 A3 A4 A5 A6m 1,2 2,3 3,4 4,5 5,6 15750 2625 750 1000 5000S 1,2 2,3 3,4 4,5 5,6 1 2 3 4 5i j mi,j si,j t 3 5 2500 3 初始化初始化:A3( A4 A5)K=4:( A3 A4 ) A5 2500 3 3750 計(jì)算A4,6的過程:i j mi,j si,j t 4 6 6250 4 初始化初始化:A4( A5

30、A6)K=5:( A4 A5 ) A6 3500 5 3500 實(shí)例分析實(shí)例分析5.所有step為3的子問題處理完畢后，數(shù)據(jù)結(jié)果如下： 0 0 157507875 0 0 2625 4375 0 0 750 2500 0 0 1000 3500 0 0 5000 0 0 1 2 3 4 5 61 2 3 4 5 6 i j 0 0 1 1 1 1 0 0 2 2 3 3 0 0 3 3 3 3 0 0 4 4 5 5 0 0 5 5 0 0 1 2 3 4 5 61 2 3 4 5 6 i j 實(shí)例分析實(shí)例分析6.繼續(xù)增加step的值分別為4，5，6，按照相似的方法得出m和s數(shù)組的右上角的數(shù)據(jù)

31、值。A1 A2 A3 A4 A5 A6Step=4:( A1 )( A2 A3 A4) (A1 A2 ) (A3 A4) (A1 A2 A3 ) ( A4) .三組三組Step=5:A1 A2 A3 A4 A5 A6( A1 )( A2 A3 A4 A5) (A1 A2 ) (A3 A4 A5) (A1 A2 A3 ) ( A4 A5)(A1 A2 A3 A4 ) ( A5)兩組兩組Step=6A1 A2 A3 A4 A5 A6( A1 )( A2 A3 A4 A5 A6) (A1 A2 ) (A3 A4 A5 A6) (A1 A2 A3 ) ( A4 A5 A6)(A1 A2 A3 A4 ) ( A5 A6) (A1 A2 A3 A4 A5 ) (A6) 只有一組只有一組實(shí)例分析實(shí)例分析6.最后的結(jié)果如下：p52