算法作業(yè)2講評(píng)

1、2008.11.21作業(yè)二講評(píng)1.xi0,1是貨柜i 的個(gè)數(shù)，倉儲(chǔ)問題：max vi xii1nn li xi D,xi 0,1i1令Ck,y是只允許裝前k 個(gè)貨柜，庫房長度為y 時(shí)的最大收益Ck, y Ck 1, yy lk D y lmaxCk 1, y, Ck 1, y l v C1, y v1偽碼略. W(n)=O(nD)kkk12. 找零錢問題nmin wi xii1nvi xi y,xi為非負(fù)整數(shù)i1Fk(y)：只使用前k 種錢，總付款為y 時(shí)零錢的最輕重量Fk ( y) minFk 1 ( y), Fk ( y vk ) wk F ( y) w y w y111v 1 標(biāo)記函數(shù)略

2、，W(n)=O(ny)實(shí)例的解是：最輕重量是6，x1=0, x2=3, x3=0, x4=0. 備忘錄略23. 雙約束0-1背包問題mi,j,k表示使用前i 種物品，背包重量限制為j,容積為k 時(shí)的最大價(jià)值mi, j, k maxmi 1, j, k, mi 1, j wi , k ci vi 如果j w1且k c1否則m1, j, k v10mi,0, k mi, j,0 0W(n)= O(nWV)34. 合并數(shù)組問題kk+1ij0n-1n-10ji4遞推公式X=x0,x1, xn1，Xij表示xi,xj合并問題，含有整數(shù)個(gè)數(shù)是nij，完成這些合并所需要最少的比較次數(shù)記作 mi,jj1j ,

3、l ik ,kmax m i maijlikj,imjn1jnmojd , al l 0mm 1amaxik,(k)ili k n1l i0 k jmi,i= 0i=0,2,n-1max)nmod0i n1T(n)=O(n3)標(biāo)記函數(shù) si,j使 mi,j 取得最小值的k55. 最長遞增子序列以xi 作為最后項(xiàng)的最長遞增子序列的長度Ci. 最大長度CC i max C j 1,j(1 j(1 j i, x j xi )i 1 1j i, xx )C 1 1C = maxCi| i=1,2,n W(n)=O(n2)ji對(duì)于給定的實(shí)例： A=,得到解是：.66. 配件選擇：按照價(jià)格從小到大對(duì)零件排

4、序. 設(shè)解向量為, xi=j 表示第i 號(hào)零件由 j 號(hào)供應(yīng)商供貨. 1xjm.結(jié)點(diǎn)表示已經(jīng)選擇了前k 號(hào)零件的供應(yīng)商,約束條件：選擇了下一個(gè)零件后總價(jià)格不超過 120.代價(jià)函數(shù)為knminwixiwjlk 1l ,2,m.i1j1其中 wjl 表示第 l 個(gè)供應(yīng)商 j 號(hào)零件的重量.樹省略，解為, 總重量為31，價(jià)值為119.7 12非負(fù)整數(shù)37. 求解34個(gè).(0,0,0), (0,0,1),(0,0,2),(0,0,3),(0,0,4),(0,0,5), (0,0,6),(0,1,0), (0,1,1),(0,1,2), (0,1,3), (0,1,4)(0,2,0),(0,2,1),(0,2,2)(0,3,0)(1,0,0),(1,0,1),(1,0,2),(1,0,3),(1,0,4)(1,1,0),(1,1,1),(1,1,2)(1,2,0),(