第六章
动态规划法
? ?
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 Cost[i] Path[i]
0
1
2
3
4
5
6
7
8 6
9 8
10 11 12 13 14 15 7
5
9
4
3
0
18 13 16 13 10 9 1
4
5
7
7
8
12 7 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]表
W1=3, V1=25 W2=2 W3=1, W4=4, W5=5 V2=20 V3=15 V4=40 V5=50 示把前i个物品装入容量为j 的背包中获得的最大价值。
最优解为（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)
0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 2 1 2 2 2 1 2 2 0 1 2 2 2 1 2 1 1x 0 0 1 1 1 1 1 1 2z 0 1 1 1 1 2 2 2
课后答案网（http://www.khdaw.com）
3y 0 4z 0 5 z 0 6 y 0 7 x 0 3 4 5 6 4 ( a ) 长度矩阵 L
( b) 状态矩阵 S
。。。。。。 第七章贪心算法 2.背包问题:
有7 个物品，背包容量W=15。将给定物品按单位重量价值从大到小排序，结果如下：
物品 1 2 3 4 5 6 7 重量(w) 2 3 5 7 1 4 1 价值(v) 10 5 15 7 6 18 3 价值/重量(v/w) 5 5/3 3 1 6 4.5 3 序号(从大 到小) 2 6 4 7 1 3 5 设背包容量为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
课后答案网（http://www.khdaw.com）
V=16+18=34 x[4]=1; c=8-5=3 V=34+15=49 x[5]=1; c=3-1=2 x[6]=2/3 ; c=0;
V=49+3=52
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.1k++;
//取下一个颜色
//用颜色k 为尽量多的顶点着色
4.2.1 若顶点i已着色，则转步骤4.2，考虑下一个顶点; 4.2.2 若图中与顶点i邻接的顶点着色与顶点i着颜色k 不冲突，
则color[i]=k;
5．输出k; 第章
回溯法
4.搜索空间
八
4.2for (i=2; i<=n; i++)
课后答案网（http://www.khdaw.com）
A 1 =1 B 2 =2
3
*
3 = 1 D
4 = 2 *
8 5 = 3
1
(a) 一个无向图
(b) 回溯法搜索空间
5
C
2
4
* * 13
最优解为（1，2，1，2，3）
5.0-1 背包问题
n
∑wx≤c
ii
1
? 可行性约束函数：
i=1
? 上界函数：
n
r=∑Vi