算法设计与分析-王红梅-课后答案网(部分)

课后答案网（://）课后答案网（://）第六章动态规划法••••P137P137P137P1372,3,42,3,42,3,42,3,4••••2.2.2.2.解答:cost[i]:cost[i]:cost[i]:cost[i]表示从顶点iiii到终点n-1n-1n-1n-1的最短路径，path[i]path[i]path[i]path[i]表示从顶点iiii到终点n-n-n-n-1111的路径上顶点iiii的下一个顶点。cost[i]=min{cij+cost[j]}cost[i]=min{cij+cost[j]}cost[i]=min{cij+cost[j]}cost[i]=min{cij+cost[j]}path[i]=path[i]=path[i]=path[i]=使cij+cost[j]cij+cost[j]cij+cost[j]cij+cost[j]最小的jjjjiiii0000111122223333444455556666777788889999101010101111111112121212131313131414141415151515Cost[i]Cost[i]Cost[i]Cost[i]1818181813131313161616161313131310101010999912121212777766668888777755559999444433330000Path[i]Path[i]Path[i]Path[i]111144445555777777778888999911111111111111111111111113131313141414141414141415151515151515150000得到最短路径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的背包中获得的最大价值。x5=1x4=0x3=0x2=1x1=1000011112222333344445555666600000000000000000000000000001111000000000000252525252525252525252525252525252222000000002020202025252525252525254545454545454545333300001515151520202020353535354040404045454545999960606060444400001515151520202020353535354040404055555555606060609999555500001515151520202020353535354040404055555555656565650000W1=3,V1=25W2=2V2=20W3=1,V3=15W4=4,V4=40W5=5V5=50最优解为（0，0，1，0，1）最优值为65.4.序列AAAA=(=(=(=(xxxx,,,,zzzz,,,,yyyy,,,,zzzz,,,,zzzz,,,,y,xy,xy,xy,x))))，BBBB=(=(=(=(zzzz,,,,xxxx,,,,yyyy,,,,yyyy,,,,zzzz,,,,xxxx,,,,zzzz))))，建立两个(m+1)(m+1)(m+1)(m+1)×(n+1)(n+1)(n+1)(n+1)的二维表LLLL和表SSSS，分别存放搜索过程中得到的子序列的长度和状态。zzzz,,,,xxxx,,,,yyyy,,,,yyyy,,,,z,z,z,z,xxxx,,,,zzzz))))0000111122223333444455556666777700001111222233334444555566667777000000000000000000000000000000000000000000000000000000000000000000001111xxxx000000001111111111111111111111111111000022221111222222222222111122222222zzzz000011111111111111112222222222222222000011112222222222221111222211113333yyyy000033334444zzzz00004444课后答案网（://）5555zzzz000055556666yyyy000066667x7x7x7x00004444(a)(a)(a)(a)长度矩阵LLLL(b)(b)(b)(b)状态矩阵SSSS。。。。。。第七章贪心算法2.背包问题:有7777个物品，背包容量====15151515。将给定物品按单位重量价值从大到小排序，结果如下：物品重量(((())))价值((((vvvv))))价值////重量((((vvvv////))))序号((((从大到小))))1111222210101010555522222222333355555/35/35/35/36666333355551515151533334444444477777777111177775555111166666666111166664444181818184.54.54.54.5333377771111333333335555设背包容量为CCCC，共有nnnn个物品，物品重量存放在数组w[n]w[n]w[n]w[n]中，价值存放在数组v[n]v[n]v[n]v[n]中，问题的解存放在数组x[n]x[n]x[n]x[n]中。按算法7.67.67.67.6————————背包问题1111．改变数组的排列顺序，使其按单位重量价值v[i]/w[i]v[i]/w[i]v[i]/w[i]v[i]/w[i]降序排列；2222．将数组x[n]x[n]x[n]x[n]初始化为0000；////////初始化解向量3333．i=1;i=1;i=1;i=1;4444．循环直到(w[i]C)(w[i]C)(w[i]C)(w[i]C)4.14.14.14.1x[i]=1;x[i]=1;x[i]=1;x[i]=1;////////将第iiii个物品放入背包4.24.24.24.2C=C-w[i];C=C-w[i];C=C-w[i];C=C-w[i];4.34.34.34.3i++;i++;i++;i++;5.5.5.5.x[i]=C/w[i];x[i]=C/w[i];x[i]=C/w[i];x[i]=C/w[i];得出,该背包问题的求解过程为::x[x[x[x[1111]=1;]=1;]=1;]=1;c=15-1=14c=15-1=14c=15-1=14c=15-1=14v=6v=6v=6v=6x[x[x[x[2222]=1;]=1;]=1;]=1;c=14-2=12c=14-2=12c=14-2=12c=14-2=12V=6+10=10V=6+10=10V=6+10=10V=6+10=10x[x[x[x[3333]=1;]=1;]=1;]=1;c=12-4=8c=12-4=8c=12-4=8c=12-4=8V=16+18=34V=16+18=34V=16+18=34V=16+18=34x[x[x[x[4444]=1;]=1;]=1;]=1;c=8-5=3c=8-5=3c=8-5=3c=8-5=3V=34+15=49V=34+15=49V=34+15=49V=34+15=49x[x[x[x[5555]=1;]=1;]=1;]=1;c=3-1=2c=3-1=2c=3-1=2c=3-1=2V=49+3=52V=49+3=52V=49+3=52V=49+3=52x[x[x[x[6666]=]=]=]=2/32/32/32/3;;;;c=0;c=0;c=0;c=0;V=52+5*2/3=156/3V=52+5*2/3=156/3V=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.37.37.3————————图着色问题1111．color[1]=1;color[1]=1;color[1]=1;color[1]=1;////////顶点1111着颜色11112222．forforforfor(i=2;(i=2;(i=2;(i=2;i=n;i=n;i=n;i=n;i++)i++)i++)i++)////////其他所有顶点置未着色状态color[i]=0;color[i]=0;color[i]=0;color[i]=0;3333．k=0;k=0;k=0;k=0;4444．循环直到所有顶点均着色4.14.14.14.1k++;k++;k++;k++;////////取下一个颜色4.24.24.24.2forforforfor(i=2;(i=2;(i=2;(i=2;i=n;i=n;i=n;i=n;i++)i++)i++)i++)////////用颜色kkkk为尽量多的顶点着色4.2.14.2.14.2.14.2.1若顶点iiii已着色，则转步骤4.24.24.24.2，考虑下一个顶点;;;;4.2.24.2.24.2.24.2.2若图中与顶点iiii邻接的顶点着色与顶点iiii着颜色kkkk不冲突，则color[i]=k;color[i]=k;color[i]=k;color[i]=k;5555．输出k;k;k;k;第八章回溯法4.搜索空间5555====333333334444222211115555AAAABBBB****CCCCDDDD8888************131313131111=1=1=1=12222=2=2=2=23333====11114444====2222(a)(a)(a)(a)一个无向图(b)(b)(b)(b)回溯法搜索空间最优解为（1111，2222，1111，2222，3333）课后答案网（://）5.0-1背包问题•可行性约束函数：•上界函数：搜索空间Cp=0,cw=0;r=70Cp=52,cw=20;r=18Cp=34,cw=10;r=36Cp=19,cw=8;r=51Cp=11,cw=5;r=591111r=6r=6r=6r=6111111111111111100000000000000000000000011111111222222222222*****13*13*13*1311114*4*4*4*2525252532*32*32*32*24242424111166662323232317171717333311111111444400001111