《算法设计与分析》(王红梅)课后习题答案 清华大学出版社 6页

'土星答案网您最真诚的朋友www.txdaan.com土星答案网团队竭诚为您服务免费提供大学课后答案|考研答案|高考答案|资格考试答案下载土星答案网www.txdaan.com 第六章动态规划法•P1372,3,4•2.解答:cost[i]表示从顶点i到终点n-1的最短路径，path[i]表示从顶点i到终点n-n-11的路径上顶点i的下一个顶点。cost[i]=min{cij+cost[j]}path[i]=使cij+cost[j]最小的ji0123456789101112131415Cost[i]1813161310912768759430Path[i]145778911111113141415150得到最短路径0->1->4->7->11->14->15,长度为183有5个物品，其重量分别是{3,2,1,4,5}，价值分别为{25,20,15,40,50}，背包的容量为6。V[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。012345600000000x1=1W1=3,V1=25100025252525x2=1W2=2V2=202002025254545x3=0W3=1,V3=1530152035404560W4=4,V4=40x4=09W5=5V5=5040152035405560x5=19土星答案网50152035405565最优解为（0，0，1，0，1）最优值为65.4.www.txdaan.com序列A=(==(=(x(xx,,z,y,z,z,y,xy,y,xx)，B=(==((z,x,y,y,z,x,z)，建立两个(m+1)×(n+1)的二维表L和表S，分别存放搜索过程中得到的子序列的长度和状态。z,x,y,y,zz,z,x,x,z)001112223334445556667700111222333444555666770000000000000000000000000000000000000000000000011xxx00000011111111111111111110002221112222222221112222zzz00011111111111122222222220001112222222221112221133yyy00344zzz004 55zzz00566yyy0067x77x7x0x04(a(a))长度矩阵L(b(b))状态矩阵S。。。。。。第七章贪心算法2.背包问题:有7个物品，背包容量W==11155。将给定物品按单位重量价值从大到小排序，结果如下：序号(从大物品重量(w)价值(v)价值/重量(v/w)到小)1210522355/36351534477175166164184.5371335设背包容量为C，共有n个物品，物品重量存放在数组w[n]中，价值存放在数组v[n]中，问题的解存放在数组x[n]中。按算法7.67.6————背包问题土星答案网1．改变数组w和v的排列顺序，使其按单位重量价值v[i]/w[i]降序排列；2．将数组x[n]初始化为0；//初始化解向量3．i=1;4．循环直到(w[i]>C)4.14.1x[i]=1;x[i]=1;//将第www.txdaan.comi个物品放入背包4.24.2C=C-w[i];C=C-w[i];4.34.3i++;i++;5.5.x[i]=C/w[i];x[i]=C/w[i];得出,该背包问题的求解过程为::x[x[111]=1;]=1;]=1;c=15-1=14c=15-1=14v=6x[x[222]=1;]=1;]=1;c=14-2=12c=14-2=12V=6+10=10x[x[333]=1;]=1;]=1;c=12-4=8c=12-4=8V=16+18=34x[x[444]=1;]=1;]=1;c=8-5=3c=8-5=3V=34+15=49x[x[555]=1;]=1;]=1;c=3-1=2c=3-1=2V=49+3=52x[x[666]=]=]=2/32/3;;c=0;c=0;c=0;V=52+5*2/3=156/3V=52+5*2/3=156/3 最优值为156/3最优解为(1,1,1,1,1,2/3,0))(x[i]按排序后物品的顺序构造)5.可以将该问题抽象为图的着色问题,活动抽象为顶点,不相容的活动用边相连(也可以将该问题理解为最大相容子集问题,重复查找剩余活动的最大相容子集,子集个数为所求).具体参见算法7.3算法7.37.3————图着色问题1．color[1]=1;//顶点1着颜色12．forfor(i=2;(i=2;(i=2;i<=n;i<=n;i<=n;i++)i++)//其他所有顶点置未着色状态color[i]=0;3．k=0;4．循环直到所有顶点均着色4.1k++;//取下一个颜色4.2forfor(i=2;(i=2;(i=2;i<=n;i<=n;i<=n;i++)i++)//用颜色k为尽量多的顶点着色4.2.1若顶点i已着色，则转步骤4.2，考虑下一个顶点;4.2.2若图中与顶点i邻接的顶点着色与顶点i着颜色k不冲突，则color[i]=k;5．输出k;第八章回溯法4.搜索空间土星答案网A11=1==11B22=2=23www.txdaan.com*C33===11D2444===22*855===3315**131133(a)一个无向图(b)回溯法搜索空间最优解为（1，2，1，2，3） 5.0-1背包问题n∑wixi≤c1•可行性约束函数：i=1•上界函数：nr=∑Vii=k+11搜索空间110Cp=11,cw=5;r=59Cp=0,cw=0;r=7022322331Cp=119,cw=8;r=5100311662422443333**01010Cp=34,cw=10;r=3614111711772222*2522553232**10110Cp=52,cw=20;r=18137,1815110*00**115*55**11882121**2622663131**112210101001r=6*6**667*1*1331919**2020**2722773030**11444**1010*8**889土星答案网2828**292299价值==5252价值==53536.该问题抽象为01背包问题，正整数为物品重量，Y为背包容量，具体代码参考01背包算法。第九章分支限界法www.txdaan.com5，解：应用贪心法求得近似解：(1,4,2,3)，其路径代价为：3+5+7+6=21，这可以作为该问题的上界。把每一个任务的最小代价相加，可以得到下界3+5+3+6=17。所以，目标函数的界为[17,21]。限界函数为：nlb=v+∑第k行的最小值k=i+1搜索空间如下： 课后答案网（http:/http://www.khdaw.com/www.khdaw.com）1startststartartlb==17117723×45×1→a2→a3→a4→allbb=17=1=177llbb==222222llbb=1==1=1818llbb==2226667812××11××1311332→b3→b4→b1→b2→b4→bllbb==242244llbb==252255llbb=1==1=1717llbb==222222llbb==252255llbb=1==1=181810×114411559××2→c3→c1→c2→cllbb==212211llbb==22233llbb==22233llbb==22222211663→dllbb==22211(×表示该结点被丢弃，结点上方的数字表示搜索顺序)6：最优解为（110101），最优值为53，搜索空间树略7：最优解为（4312），最优值为40，搜索空间树略略土星答案网www.txdaan.com'