算法作業(yè)2講評

1、2008.11.21作業(yè)二講評1.xi0,1是貨柜i 的個數(shù)，倉儲問題：max vi xii1nn li xi D,xi 0,1i1令Ck,y是只允許裝前k 個貨柜，庫房長度為y 時的最大收益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為非負整數(shù)i1Fk(y)：只使用前k 種錢，總付款為y 時零錢的最輕重量Fk ( y) minFk 1 ( y), Fk ( y vk ) wk F ( y) w y w y111v 1 標記函數(shù)略

2、，W(n)=O(ny)實例的解是：最輕重量是6，x1=0, x2=3, x3=0, x4=0. 備忘錄略23. 雙約束0-1背包問題mi,j,k表示使用前i 種物品，背包重量限制為j,容積為k 時的最大價值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ù)個數(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)標記函數(shù) si,j使 mi,j 取得最小值的k55. 最長遞增子序列以xi 作為最后項的最長遞增子序列的長度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對于給定的實例： A=,得到解是：.66. 配件選擇：按照價格從小到大對零件排

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