8. 考虑使用动态规划方法求解下列问题：
01背包数据如下表，求：能够放入背包的最有价值的物品集合。
物品 i 1 2 3 4
如设： V(i, j) —— 前 i 个物品中能够装入承重量 j 的背包中的最大总价值。请将如下递推式填写完整：
V(0, j) = 0（0个物品），V(i, 0) = 0（承重量0）
V(i, j) = V(i-1, j) 第 i 个物品不能装入， j < wi （超重）
V(i, j) = max { , } j > wi （不超重） i在最优子集中 i不在最优子集中
自底向上：按行或列填写下表。 V i=0 1 2 3 4
重量 wi w1=2 w2=1 w3=3 w4=2 价值 vi v1=12 v2=10 v3=20 v4=15 承重量 W W=5 j=0 0 0 0 0 0 1 0 2 0 3 0 4 0 5 0
答：
V(0, j) = 0（0个物品），V(i, 0) = 0（承重量0）
V(i, j) = V(i-1, j) 第 i 个物品不能装入， j < wi （超重）
V(i, j) = max { vi + V(i-1,j-wj) , V(i-1, j) } j > wi （不超重） i在最优子集中 i不在最优子集中 V i=0 1 2 3 4
9.请画出4皇后问题的解空间树和搜索空间树： 解空间树：
j=0 0 0 0 0 0 1 0 0 10 10 10 2 0 12 12 12 15 3 0 12 22 22 25 4 0 12 22 30 30 5 0 12 22 32 37
用回溯法的搜索空间树：
10.考虑用分支限界解0-1背包问题
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
示例：n=3, C=30, w={16, 15, 15}, v={45, 25, 25} 求：1、问题的解空间树
2、约束条件 2、如何剪枝？
解：
问题的解空间树：
约束条件：
如何剪枝？：
设r是当前尚未考虑的剩余物品价值总和；Cv是当前价值；bestv是当前最优价值。
当r＋Cv≤bestv时，可剪去右子树。
11，请画出n=3的0-1背包问题的解空间树和当三个物品的重量为{20, 15, 10}，价值为{20,
30, 25}，背包容量为25时搜索空间树。 答：
解空间树：
?wxi?1nii?c1
1
1
0
2
1
0
1
9
0
3
0
1
6
10
0
3
0
1
0
1
1
4
5
7 8 11
12 14 15
搜索空间树：
1
1
0
2
1 1
0
10
0
1
0 1
9
0 13
1
0
6
不可行解
8 价值=20
11
价值=55
12 价值=30
14 价值=25
15 价值=0
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算法分析复习(6)在线全文阅读。
相关推荐：