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

课后答案网（） 课后答案网（） 第六章 动态规划法 P137 2 ,3, 4 2.解答:cost[i]表示从顶点 i 到终点 n-1 的最短路径，path[i]表示从顶点 i 到终点 n-1 的路径上顶点 i 的下一个顶点。 cost[i]=min{cij+cost[j]} path[i]= 使 cij+cost[j] 最小的 j i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Cost[i] 18 13 16 13 10 9 12 7 6 8 7 5 9 4 3 0 Path[i] 1 4 5 7 7 8 9 11 11 11 13 14 14 15 15 0 得到最短路径 0-1-4-7-11-14-15 , 长度为 18 3 有 5 个物品，其重量分别是{3, 2, 1, 4,5}，价值分别为{25, 20, 15, 40, 50}，背包的容量为 6。 V[i][j]表示把前 i 个物品装入容量为 j 的背包中获得的最大价值。 W1=3,V1=25W2=2V2=20W3=1,V3=15W4=4,V4=40W5=5V5=50最优解为（0，0，1，0，1）最优值为 65. 4. 序列A=(x, z, y, z, z, y,x)，B=(z, x, y, y, z, x, z)，建立两个(m+1)×(n+1)的二 维表 L和表 S，分别存放有哪些信誉好的足球投注网站过程中得到的子序列的长度和状态。 z, x, y, y, z,x, z) 0123456701234567000000000000000001x001111111021222122z011112222012221213y034z045 z 0 5 6 y 0 6 x 7 0 4 ( a ) 长度矩阵 L ( b ) 状态矩阵 S 。。。。。。 第七章 贪心算法 2.背包问题: 有 7 个物品，背包容量W=15。将给定物品按单位重量价值从大到小排序，结果如下： 物品重量(w)价值(v)价值/重量(v/w)序号 (从大 到小)1210522355/36351534477175166164184.5371335设背包容量为 C，共有 n 个物品，物品重量存放在数组 w[n]中，价值存放在数组 v[n]中，问题的解存放在数组 x[n]中。 按算法 7.6——背包问题 1．改变数组 w 和 v 的排列顺序，使其按单位重量价值 v[i]/w[i]降序排列； 2．将数组 x[n]初始化为 0； //初始化解向量 3．i=1; 4．循环直到( w[i]C ) 4.1 x[i]=1; //将第 i 个物品放入背包 4.2 C=C-w[i]; 4.3 i++; 5. x[i]=C/w[i]; 得出,该背包问题的求解过程为:: x[1]=1; c=15-1=14 v=6 x[2]=1; c=14-2=12 V=6+10=10 x[3]=1; c=12-4=8 V=16+18=34 x[4]=1; c=8-5=3 V=34+15=49 x[5]=1; c=3-1=2 V=49+3=52 x[6]=2/3 ; c=0; V=52+5*2/3=156/3 最优值为 156/3 最优解为 (1,1,1,1,1,2/3,0)) (x[i]按排序后物品的顺序构造) 5.可以将该问题抽象为图的着色问题,活动抽象为顶点,不相容的活动用边相连 (也可以将该问题理解为最大相容子集问题,重复查找剩余活动的最大相容子集,子集个数为所求). 具体参见算法 7.3 算法 7.3——图着色问题 1．color[1]=1; //顶点 1 着颜色 1 2．for (i=2; i=n; i++) //其他所有顶点置未着色状态 color[i]=0; 3．k=0; 4．循环直到所有顶点均着色 4.1 k++; //取下一个颜色 4.2 for (i=2; i=n; i++) //用颜色 k 为尽量多的顶点着色 4.2.1 若顶点 i 已着色，则转步骤 4.2，考虑下一个顶点; 4.2.2 若图中与顶点 i 邻接的顶点着色与顶点 i 着颜色 k 不冲突， 则 color[i]=k; 5．输出 k; 第八章回溯法 4.有哪些信誉好的足球投注网站空间 3 4 2 1 5 5 = 3 A B