发布时间 : 星期日 文章算法设计与分析复习题目及答案资料更新完毕开始阅读
10.考虑用分支限界解0-1背包问题
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
示例：n=3, C=30, w={16, 15, 15}, v={45, 25, 25} 求：1、问题的解空间树
2、约束条件 2、如何剪枝？
解：
问题的解空间树：
约束条件： 如何剪枝？：
?wxi?1nii?c1设r是当前尚未考虑的剩余物品价值总和；Cv是当前价值；bestv是当前最优价值。
当r＋Cv≤bestv时，可剪去右子树。
11，请画出用回溯法解n=3的0-1背包问题的解空间树和当三个物品的重量为{20, 15, 10}，
价值为{20, 30, 25}，背包容量为25时搜索空间树。 答：
解空间树：
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
9
0
10
0
1
0
1
1
0 13
0
6
8 价值=20
11
价值=55
12 价值=30
14 价值=25
15 价值=0
不可行解