算法分析期末考試集答案

1、算法分析與設(shè)計?一、 解答題1. 機器調(diào)度問題。問題描述：現(xiàn)在有 n 件任務(wù)和無限多臺的機器，任務(wù)可以在機器上得到 處理。每件任務(wù)的開始時間為Si，完成時間為f i, SiVfi。s i, fi為處理任 務(wù) i 的時間范圍。兩個任務(wù) i ， j 重疊指兩個任務(wù)的時間范圍區(qū)間有重疊， 而并非指 i, j 的起點或終點重合。例如：區(qū)間 1, 4與區(qū)間2, 4重疊, 而與4, 7不重疊。一個可行的任務(wù)分配是指在分配中沒有兩件重疊的任務(wù) 分配給同一臺機器。因此,在可行的分配中每臺機器在任何時刻最多只處理 一個任務(wù)。最優(yōu)分配是指使用的機器最少的可行分配方案。問題實例：假設(shè)任務(wù)占用的時間范圍是 1 , 4

2、, 2, 5, 4, 5, 2, 6, 4, 7 ,那么按時完成所有任務(wù)最少需要幾臺機器？(提示：使用貪心 算法)畫出工作在對應(yīng)的機器上的分配情況。2. 非齊次遞歸方程：f(n) bf(n 1) g(n)，其中，b、c是常數(shù)，g(n)f (0) cn是 n 的某一個函數(shù)。那么 f(n) 的非遞歸表達(dá)式為： f(n) cbnbn ig(i) 。i1現(xiàn)有Hanoi塔問題的遞歸方程為：h(n) 2h(n 1) 1，求h(n)的非遞歸表 h(1) 1達(dá)式。解：禾U用給出的關(guān)系式，此時有：b=2, c=1, g(n)=1,從n遞推到1，有：n1 h(n) cbn 1bn1 ig(i)i1n 1 n 22

3、2n 1 2n 2 . 22 2 1n2n 13. 單源最短路徑的求解。問題的描述：給定帶權(quán)有向圖(如以下圖所示)G =(V,E)，其中每條邊的權(quán)是非負(fù)實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其它 各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單 源最短路徑問題解法：現(xiàn)采用Dijkstra 算法計算從源頂點1到其它頂點間最短路徑。請將 此過程填入下表中。迭代Sudist2dist3dist4dist5初始1-10maxi nt3010012344. 請寫出用回溯法解裝載問題的函數(shù)。裝載問題：有一批共n個集裝箱要裝上2艘載重量分別為cl和c2的輪船，n

4、Wi C1 C2其中集裝箱i的重量為wi，且i 1。裝載問題要求確定是否有一個合理的裝載方案可將這n個集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。解: void backtrack (int i)用分支限界法解裝載問題時，對算法進(jìn)行了一些改良，下面的程序段給出了 改良局部；試說明斜線局部完成什么功能，以及這樣做的原因，即采用這樣的方 式，算法在執(zhí)行上有什么不同。/檢查左兒子結(jié)點Type wt = Ew + wi; /左兒子結(jié)點的重量if (wt bestw) bestw = wt;/參加活結(jié)點隊列if (i bestw & i 0故Ew+rbestw總是成立。也就 是說，此時右子樹測試不起

5、作用。為了使上述右子樹測試盡早生效，應(yīng)提早更新bestw。又知算法最終找到的最優(yōu)值是所求問題的子集樹中所有可行結(jié)點相應(yīng)重量的最大值。而結(jié)點所相應(yīng)得重量僅在搜索進(jìn)入左子樹是增加，因此，可以在算法每一次進(jìn)入左子樹時更新 bestw的值。7.最長公共子序列問題：給定2個序列X=x1,x2,xm和Y=y1,y2,yn ， 找出X和丫的最長公共子序列。由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān)系。用cij記錄序列Xi和Yj的最長公共子序列的長度。其中，Xi=x1,x2,xi ; Yj=y1,y2,yj。當(dāng) i=0 或 j=0 時，空序列是 Xi 和 Yj 的最長公共子序列。故此時Cij

6、=0 。其它情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立0i 0,j 0遞歸關(guān)系如下：ci jci 1j 1 1i, j 0;xi ymaxcij 1,ci1j i,j 0必 在程序中，bij 記錄Cij的值是由哪一個子問題的解得到的。(1)請?zhí)顚懗绦蛑械目崭瘢允购瘮?shù)LCSLe ngth完成計算最優(yōu)值的功能。void LCSLength(int m , int n , char *x , char *y , int *c, int *b)int i , j；for (i = 1; i = m; i+) ci0 = 0;for (i = 1; i = n; i+) c0i = 0;for (i = 1; i

7、 = m; i+)for (j = 1; j =cij-1) cij=ci-1j; bij=2;else cij=cij-1; bij=3;(2)函數(shù)LCS實現(xiàn)根據(jù)b的內(nèi)容打印出Xi和Yj的最長公共子序列。請?zhí)?寫程序中的空格，以使函數(shù)LCS完成構(gòu)造最長公共子序列的功能(請 將bij的取值與(1)中您填寫的取值對應(yīng)，否那么視為錯誤)。void LCSint i，int j ，char *x，int *b)if (i =0 | j=0) retur n;if (bij= 1) LCS( i-1，j-1，x, b); cout0 ) printf(%dn ,k);f(k-1);f(k-1);、復(fù)雜

8、性分析1、MERGESORT(lo，w high) if lowhigh ；then midJ (low , high)/2 ;MERGESORT(low ， mid) ；MERGESORT(mid+1 ， high) ；MERGE(low ， mid， high) ； endifend MERGESORT 答: 1 、 遞歸方程T(n)設(shè) n=2k 解遞歸方程：2T(n/2) cn n 1T(n) 2(2T(n/4) cn/2)4T(n/4) 2cncn2k T(1) kcn an cnlogn2、procedure S1(P ， W， M， X， n)i J 1; a J 0while i

9、 M then return endifaJ a+iiJ i+1 ;repeatend解： i J 1 ;s J 0 時間為： O(1) while i v repeatloop p j p-1 until A(p)w v repeatif ipthen call INTERCHANGE(A(i),A(p)else exitendifrepeatA(m)jA(p);A(p)jvEnd PARTITION 解：最多的查找次數(shù)是 p-m+1 次F1(n)if n1 時 F1(n) 的時間復(fù)雜度與 F2(2,n,1,1) 的時間復(fù)雜度相同即為為MAX(A,n,j)xmax jA(1);j j1jA(

10、i); j ji;endif時間為： O(1)循環(huán)最多 n-1 次for ij 2 to n doif A(i)xmax then xmax repeat end MAX解：xmaxJ A(1);j j 1 for ij 2 to n do所以 總時間為 :T(n)=O(1)+ (n-1)O(1)= O(n)BINSRCH(A,n,x,j)integer low,high,mid,j,n;low j1;high jnwhile loww high domidj|_(low+high)/2 _|case:xA(mid):low J mid+1:else:j j mid; returnendcas

11、e repeat j J 0 end BINSRCH解: log n+1三、算法理解1、寫出多段圖最短路經(jīng)動態(tài)規(guī)劃算法求解以下實例的過程，并求出最優(yōu)值。C(1,2)=3， C(1,3)=5C(2,6)=8，C(2,7)=4C(5,8)=4， C(6,8)=5 解：Cost(4,8)=0Cost(3,7)= C(7,8)+0=6Cost(3,6)= C(6，C(1,4)=2，C(3,5)=5，C(3,6)=4，C(7,8)=6,C(4,5)=2 ，C(4,6)=1，D5=88)+0=5, D6=8Cost(3,5)= C(5，8)+0=4 D7=8，5)+ Cost(3,5)，7)+ Cost(

12、3,7)Cost(2,4)= minC(4， 6)+ Cost(3,6), C(4=mi n1+ 5, 2+4=6 D4=6Cost(2,3)= minC(3，6)+ Cost(3,6) =mi n4+5=9 D3=5Cost(2,2)= minC(2，6)+ Cost(3,6), C(2=min 8+5, 4+6=10 D2=7Cost(1,1)= mi nC(1,2)+ Cost(2,2), C(1,3)+ Cost(2,3), C(1,4)+ Cost(2,4)=min 3+10, 5+9,2+6= 8D1=41 t82、寫出maxmin算法對以下實例中找最大數(shù)和最小數(shù)的過程。 數(shù)組 A

13、=(48,12,61,3,5,19,32,7)解：寫出maxmin算法對以下實例中找最大數(shù)和最小數(shù)的過程。 數(shù)組A=()1、48,12,61,3,5,19,32,72、48,1261,35,1932,73、48 61, 123 1932, 574、61 32355、61 3次被分割的過程。3、快速排序算法對以下實例排序，算法執(zhí)行過程中，寫出數(shù)組A第A=(65,70,75,80,85,55,50,2)解：第一個分割元素為65(1) (2) (3) (4)(6)(8) i p65707580855550228652758085555070376525080855575704665250558580

14、7570465570758085655024、 歸并排序算法對以下實例排序，寫出算法執(zhí)行過程。A=(48,12,61,3,5,19,32,7)解: 48,12,61,35,19,32,748,1261,35,1932,712,483,615,197,323, 12, 48, 615,7,19，323,5, 7,12，19，32，48,615、 寫出圖著色問題的回溯算法的判斷Xk是否合理的過程。解：i 0while i P(i+1)/W(i+1) 的順序。CU 25,X 0W1 CU: x1 1; CU CU-W1=13;W2CU: x3 CU/ W3=3/8;實例的解為：(1 , 1, 3/8

15、 , 0)11、有一個有序表為1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，當(dāng)使用二分 查找值為82的結(jié)點時，經(jīng)過多少次比擬后查找成功并給出過程。解：有一個有序表為1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100，當(dāng)使用二分 查找值為82的結(jié)點時，經(jīng)過多少次比擬后查找成功并給出過程。一共要要執(zhí)行四次才能找到值為82的數(shù)。12、使用prim算法構(gòu)造出如以下圖 G的一棵最小生成樹。dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=

16、5; dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=6 解：使用普里姆算法構(gòu)造出如以下圖G的一棵最小生成樹。dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=613、有如下函數(shù)說明int f(int x,i nt y)f=x Mod y +1;后，k的值是多少并寫出詳細(xì)過程。后，k的值是多少并寫出詳細(xì)過程。 a=10,b=4,c=5 那么執(zhí)行

17、 k=f(f(a+c,b),f(b,c)解：有如下函數(shù)說明int f(int x,i nt y)f=x Mod y +1; a=10,b=4,c=5 那么執(zhí)行 k=f(f(a+c,b),f(b,c) K的值是5 14、McCathy函數(shù)定義如下： 當(dāng) x100 時 m(x)=x-10;當(dāng) x100 時 m(x)=x-10;當(dāng) x100) return(x-IOO);elsey=m(x+11);return (m(y); 15、設(shè)計一個算法在一個向量A中找出最大數(shù)和最小數(shù)的元素。解：設(shè)計一個算法在一個向量A中找出最大數(shù)和最小數(shù)的元素。Void maxmi n(A,n)Vector A;int n

18、;int max,mi n,i;max=A1;mi n=A1;for(i=2;imax)max=Ai; else if(Ai t2 tn排序2) S1:m清零j - 0設(shè)有n種面值為：d1 d2 dn的錢幣，需要找零錢M,如何選擇錢幣dk，的數(shù)目兀，滿足d1X X +dnX % M，使得X +最小請選擇貪心策略，并設(shè)計貪心算法。 解：貪心原那么：每次選擇最大面值硬幣。CU- M;i - 1;X- 0有 n 個物品，n=7,利潤為 P=(10,5,15,7,6,18,3) ，重量W=(2,3,5,7,1,4,1)，背包容積 M=15,物品只能選擇全部裝入背包或不裝入背包，設(shè)計貪心 算法，并討論是

19、否可獲最優(yōu)解。解：定義結(jié)構(gòu)體數(shù)組 G,將物品編號、利潤、重量作為一個結(jié)構(gòu)體：例如 Gk=1,10,2 求最優(yōu)解，按利潤/重量的遞減序，有5,6,1,6 1,10,2,56,18,4,9/2 3,15,5,3 7,3,1,32,5,3,5/3 4,7,7,1算法procedure KNAPSACK(P , W M X n)設(shè)計只求一個哈密頓環(huán)的回溯算法。解： Hamiltonian(n)k 1; xk 0;While k0 doxk xk+1;while B(k)=false and xk n doxk xk+1; repeatIf xk n thenif k=n then print x; r

20、eturnelse k k+1; xk 0; endifelse k k-1endifrepeatendprocedure B(k) Gxk-1,xk 豐 1 then return false;for i 1 to k-1 doif xi=xk then return false;endifrepeatreturn true;5利用對稱性設(shè)計算法，求n 為偶數(shù)的皇后問題所有解。解：利用對稱性設(shè)計算法，求 n 為偶數(shù)的皇后問題所有解。procedure NQUEENS1(n)0log n 5;(100n2)a2f(n) (g(n) f (n) (g(n) f(n) log n2;g(n) f(

21、n) 2n;g(n) 100n2; f(n) 2n;g(n) 3n; logn2(log n 5) 2n2n(3n) R r1,r2,.,rn) n r1,r2,.,rn R(4 分)coutendl;else for(int i=k;i=m;i+)if(ok(list,k,i)swap(listk,listi);Perm(list,k+1,m);swap(listk,listi); .( 8 分);其中 ok 用于判別重復(fù)元素。Templateint ok(Type list,int k,int i)if(ik)for(int t=k;tI;t+)if(listt= =listi) retu

22、rn 0;return 1; .( 13 分)3、試用分治法對一個有序表實現(xiàn)二分搜索算法。 (12 分)解：解答如下：Templateint BinarySearch(Type a,const Type& x,int n) (4 分)if(x= =amiddle) return middle+1;if(xamiddle) left=middle+1; . ( 8 分)else right=middle-1;return -1; .( 12 分)4、試用動態(tài)規(guī)劃算法實現(xiàn) 0-1 閉包問題。(15 分)解：解答如下：Templatevoid Knapsack(Type v,int w,int c,

23、int n,Type *m)Int jMax=min(wn-1,c);for(int j=0;j=jMax;j+) mnj=0;for(int j=wn;j1;i-)jMax=min(wi-1,c);for(int j=0;j=jMax;j+) mij=mi+1j;for(intj=wi;j=w1) m1c=max(m1c,m2c-w1+v1); ( 10 分)TemplateVoid Traceback(Type *m,int w,int c,int n,int x)for(int i=1;in;i+)ifmic= =mi+1c xi=0; 12 分else xi=1,c-=wi;xn=mn

24、c?1:0; .15 分5、試用貪心算法求解以下問題：將正整數(shù) n 分解為假設(shè)干個互不相同的自然數(shù)之 和，使這些自然數(shù)的乘積最大。 15 分解：解答如下：void dicomp(int n,int a)k=1;if(n3) a1=0;return;if(nak)k+;ak=ak-1+1;n-=ak; .( 10 分)if(n= =ak) ak+;n-;for(int i=0;in;i+) ak-i+; .( 15 分)6試用動態(tài)規(guī)劃算法實現(xiàn)最大子矩陣和問題：求m n矩陣A的一個子矩陣，使其各元素之各為最大。 (15 分)解：解答如下：int MaxSum2(int m,int n,int *a

25、)int sum=0;int *b=new intn+1;for(int i=1;i=m;i+)for(int k=1;k=n;k+) bk=O; . ( 5分)for(int j=i;j=m;j+)for(int k=1;ksum) sum=max;return sum; .( 10 分)int MaxSum(int n,int *a)int sum=0,b=0;for(int i=1;i0) b+=ai;else b=ai;if(bsum) sum=b;Return sum; . ( 15 分)7、試用回溯法解決以下整數(shù)變換問題：關(guān)于整數(shù)i 的變換 f 和 g 定義如下：f(i) 3i;g

26、(i)i/2。對于給定的兩個整數(shù)n和m,要求用最少的變換f和g變換次數(shù)將 n 變?yōu)?m 。(18 分)解：解答如下：void compute。k=1;while(!search(1,n)k+;if(kmaxdep) break;init();； .( 6 分)if(found) output();else coutNo Solution! k) return false；12分)for(int i=0；i2；i+)int n1=f(n,i)；tdep=i；if(n1= =m|search(dep+1,n1)Found=true；Out()；return true；return false; .

27、( 18 分)一、排序和查找是經(jīng)常遇到的問題。按照要求完成以下各題：(20 分)(1) 對數(shù)組 A=15, 29, 135, 18, 32, 1 , 27, 25, 5，用快速排序方法將其排成遞減序。2) 請描述遞減數(shù)組進(jìn)行二分搜索的根本思想，并給出非遞歸算法。3) 給出上述算法的遞歸算法。4) 使用上述算法對( 1)所得到的結(jié)果搜索如下元素，并給出搜索過程：18，31，答案：( 1 )第一步： 15 29 135 18 32 1 27 25 5第二步： 29 135 18 32 272515 1 5【 1分】第三步： 135 32 29 18 272515 5 1【 1分】第四步： 135

28、32 29 27 251815 5 1【 1分】(2) 根本思想：首先將待搜索元素v與數(shù)組的中間元素A n進(jìn)行比擬，如果v A -,2 2那么在前半局部元素中搜索v ;假設(shè)v A n，那么搜索成功；否那么在后半局部數(shù)組中搜索v?！?2分】非遞歸算法：輸入：遞減數(shù)組 Aleft:right，待搜索元素V?！?分】輸出：v在A中的位置pos，或者不在A中的消息(-1 )?！?分】步驟：【3分】int Bin arySearch(i nt A,i nt left,i nt right, int v)int mid;while (leftAmid) right=mid-1;else left=mid+

29、1;return -1;(3) 遞歸算法：輸入：遞減數(shù)組 Aleft:right，待搜索元素V?！?分】輸出：v在A中的位置pos，或者不在A中的消息(-1 )?！?分】步驟：【3分】int Bin arySearch(i nt A,i nt left,i nt right, int v)int mid;if (leftAmid) retur n Bin arySearch(A,left,mid-1,v);else return Bin arySearch(A,mid+1,right,v);elsereturn -1;(4) 搜索18：首先與27比擬，1827,在前半局部搜索；再次 32比擬，

30、3129，此時只有一個元素，未找到，返回-1?！?分】搜索135:首先與27比擬，13527,在前半局部搜索；再次 32比擬，13532，在前 半局部搜索；與135比擬，相同，返回 0?！?分】二、對于以下圖使用 Dijkstra 算法求由頂點a到頂點h的最短路徑。20分。答案：用Vi表示已經(jīng)找到最短路徑的頂點，V2表示與Vi中某個頂點相鄰接且不在 V中的頂點；E表示參加到最短路徑中的邊，E2為與Vi中的頂點相鄰接且距離最短的路徑。【1分】步驟V 1V2 E1E21.abab2.a,bdabbd3.a,b,dc,fab,bddc,df4.a,b,d,cfab,bddf5.a,b,c,d,fea

31、b,bd,dc,dffe6.a,b,c,d,e,fgab,bd,dc,df,feeg7.a,b,c,d,e,f,ghab,bd,dc,df,fe,eggh8.a,b,c,d,e,f,g,h ab,bd,de,df,fe,eg,gh 【以上每步2分】結(jié)果:從a到h的最短路徑為a b d f e gh ,權(quán)值為18?！?分】三假設(shè)有7個物品，它們的重量和價值如下表所示。假設(shè)這些物品均不能被分割，且背包容量 W 150，使用回溯方法求解此背包問題。請寫出狀態(tài)空間搜索樹20分。物品ABC重量353060價值104030DEFG5040102550354030答案：求所有頂點對之間的最短路徑可以使用Di

32、jkstra 算法，使其起始節(jié)點從a循環(huán)到h，每次求起始節(jié)點到其他節(jié)點的最短路徑，最終可以求得所有頂點對之間的最短路徑。【2分】三、按照單位效益從大到小依次排列這 7個物品為：FBGDECA將它們的序號分別記為 17。 那么可生產(chǎn)如下的狀態(tài)空間搜索樹。其中各個節(jié)點處的限界函數(shù)值通過如下方式求得：【排序1分】X7X21X2X41aX4xiQidgX3X,0【狀態(tài)空間搜索樹及其計算過程17分，每個節(jié)點1分】a.404030503540190.625(1,1,1,1-,0,0)8150 11574040305030177.5 (1,1,1,1,0,0)60124040305010170(1,1,1,

33、1,0,0,1)150 10534040303530167.5(1,1,1,0,1,_,0)604150 13014040503530175(1,1,0,1,10)60315013040405035 1035170.71(1,1,0,1,1,0石)150115b.c.d.e.f.(1,1,0,1,0,1,0)g.4040 50 30160h.4040 35 30 10 150 140146.8535(1,1,0,0,1,1,|)i.150 125u40 30 50 35 30 167.5(何乙詩,。)60j.15014540 30 50 35 30157.5(0,1,111丄,0)1260在Q

34、處獲得該問題的最優(yōu)解為1,1,1,1,0,0,1,背包效益為170。即在背包中裝入物品G D、A時到達(dá)最大效益，為170,重量為150。【結(jié)論2分】 Ak(aij(k)n*r11，k=1， 2， 3， 4， 5， 6，1=5，2=10，3=3，r4=12， r5=5, r6=50，7=6，求矩陣鏈積 AX A.X AX AX A5X A的最正確求積順序。要求：給出計算步驟20分 答案：使用動態(tài)規(guī)劃算法進(jìn)行求解。求解矩陣為：【每個矩陣18分】123456101503304051655202120360330243019503018093017704030001860501500601234561

35、012420222230p4440445060因此，最正確乘積序歹y 為(AA2)(氏A (AA6),共執(zhí)行乘法2021次?！窘Y(jié)論2分】七、算法設(shè)計題(此題10分)通過鍵盤輸入一個高精度的正整數(shù)n(n的有效位數(shù)w 240)，去掉其中任意s個數(shù)字后，剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小?！緲永斎搿?78543S=4【樣例輸出】13六、算法設(shè)計題(此題15分)(1) 貪心算法 O (nlog (n)首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。假設(shè)將這種物品全部裝入

36、背包后，背包內(nèi)的物品 總重量未超過 C,那么選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策 略一直地進(jìn)行下去，直到背包裝滿為止。具體算法可描述如下：void Knapsack(int n,float M,float v,float w,float x)Sort( n,v,w);int i;for (i=1;i=n ;i+) xi=0;float c=M;for (i=1;ic) break;xi=1; c-=wi;if (i=n) xi=c/wi;(2) 動態(tài)規(guī)劃法 0( nc)m(i , j)是背包容量為j，可選擇物品為i , i+1 ,，n時0-1背包問題的最優(yōu)值。由 0-1背包問

37、題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i , j)的遞歸式如下。m()maxm(i 1，j)，m(i 1，j w Vij Wim(i 1,j)0 j Wim(n, j)VnWnWnvoid KnapSack(int v,int w,int c,int n,int m11) int jMax=mi n(w n-1,c);for (j=O;j=jMax;j+) /*m(n,j)=0 0=jwn*/ m nj=O;for (j=w n ;j=w n*/ m nj=v n ;for (i=n-1;i1;i-) int jMax=mi n(wi-1,c);for (j=0;j=jMax;j+) /*m(i,j)=m(i+1,j) 0=jwi*/ mij=mi+1j;for (j=wi;j=w n*/ mij=max(mi+1j,mi+1j-wi+vi);m1c=m2c;if(c=w1) m1c=max(m1c,m2c-w1+v1