北大屈婉玲算法分析与设计 习题解答2.pdf

《北大屈婉玲算法分析与设计 习题解答2.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、作业二1.x＝010,1是货柜i的个数，仓储问题：inmax∑lixii=1n∑lixi≤L,xi=0,1i=1令C[k,y]是只允许装前k个货柜，库房长度为y时的最大收益⎧C[k−1,y]y1max{C[k−1,y],C[k−1,y−l]+l}L≥y≥l⎩k+k≥≥kC[1,y]=l1伪码略.W(n)=O(nD)12.找零钱问题nmin∑wixii=1n∑vixi=y,xi为非负整数i=1F(y)：只使用前k种钱，总付款为y时零钱的最轻重量kF(y)=min{F(y),F(y−v)+w}kk−1kkk⎢y⎥F(y)=w⎥=wy11⎢1v⎣

2、1⎦标记函数略，W(n)=O(ny)实例的解是：最轻重量是6，x=0,x=3,x=0,x=0.备忘录略123423.作业调度与0-1背包问题类似，使用动态规划方法.令N(d)表示对作业集{1,2,…,j}，结束时间为d的最优调度的j效益，那么N(d)=max{N(d),N(d−t(j))+v}d≥t(j)jj−1j−1jN(d)=N(d)d0⎩0t(1)>d自底向上计算，存储使用备忘录。可以使用标记函数B(j)记录使得N(d)达到最大是否N(d)=N(d).如果不等，B(j)=1，jjj−1否则为0.时间W(n)

3、=O(nD)3伪码Job(t,v,D)输入：加工时间t[1..n]，效益v[1..n]，结束时间D输出：最优效益N[n,D],标记函数B，解是{k

4、B[k]=1}1.for1.ford←1to1tot[1]−12.N[1,d]←0,B[1]←03.ford←t[1]toD4.N[1,d]←v[1],B[1]←15.fork←2ton6f6.forord←1to1toD7.N[k,d]←N[k−1,d]8.B[k]←09.ifd≥t[k]andN[k−1,d−t[k]]+v[k]>N[k−1,d]10.thenN[k,d]←N[k−1,d−t[k]]+v[k]11.B

5、[k]←144.双约束0-1背包问题m[i,j,k]表示使用前i种物品，背包重量限制为j,容积为k时的最大价值m[i,j,k]=max{m[i−1,j,k],m[i−1,j−w,k−c]+v}iiij≥wandk≥ciim[i,j,k]=m[i−1,j,k]j

6、j⎧j⎪max{m[i,k]+m[k+1,j]}+∑alij⎪i≤k≤n−1l=il=0⎩0≤k