算法作业2讲评

1、2008.11.21作业二讲评1.xi0,1是货柜i 的个数，仓储问题：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为非负整数i1Fk(y)：只使用前k 种钱，总付款为y 时零钱的最轻重量Fk ( y) minFk 1 ( y), Fk ( y vk ) wk F ( y) w y w y111v 1 标记函数略

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. 合并数组问题kk+1ij0n-1n-10ji4递推公式X=x0,x1, xn1，Xij表示xi,xj合并问题，含有整数个数是nij，完成这些合并所需要最少的比较次数记作 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)标记函数 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、序. 设解向量为, xi=j 表示第i 号零件由 j 号供应商供货. 1xjm.结点表示已经选择了前k 号零件的供应商,约束条件：选择了下一个零件后总价格不超过 120.代价函数为knminwixiwjlk 1l ,2,m.i1j1其中 wjl 表示第 l 个供应商 j 号零件的重量.树省略，解为, 总重量为31，价值为119.7 12非负整数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),(