算法设计与分析复习题目及答案

9.请画解空间解空间用回溯10.考题

给

V i=0 1 2 3 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 出用回溯法解4皇后问题的树和搜索空间树： 树：

法的搜索空间树： 虑用分支限界解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时搜索空间树。 答：

解空间树：

1 1

0

2 1

0

1

9 0

3 6 10 3 0

1 0 1 0

1 0 1

4 5 7 8 11 12 14 15

搜索空间树：

1

1 0

2 1

0

10 0

1

0 1

9 0 13 1

0

6 1

8 不可行解

价值=20

11 价值=55

12 价值=30

14 价值=25

15 价值=0