算法设计与分析复习题目及答案 下载本文

用回溯法的搜索空间树:

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